Merge two data frames based on a pattern match and two additional conditions

Question

I have two data frames as below:

df1
  City   State   Year
Modesto    CA    2000
Modesto    CA    2001
Anchorage  AK    1999
Anchorage  AK    2000
Greensboro NC    1998
Greensboro NC    1999
Las Vegas  NV    2001
Fort Worth TX    2002

df2
              Agency               State  Year  
Pasadena Police Dept                CA    1999
Pasadena Police Dept                CA    2000
Las Vegas Metropolitan Police Dpt   NV    2001
Modesto Police                      CA    2000
Modesto Police                      CA    2001
City of Fort Worth Police Dept      TX    2002

I need to merge them on all 3 columns, the issue is searching through the Agency column for matches to the city column.

For this example this is what my output would look like:

Output
              Agency                City      State  Year  
Modesto Police                     Modesto     CA    2000
Modesto Police                     Modesto     CA    2001
Las Vegas Metropolitan Police Dpt  Las Vegas   NV    2001
City of Fort Worth Police Dept     Fort Worth  TX    2002

As you can see the verbiage of the Agency column is not consistent with how the departments are titled as well as the position of the city name in the string.

I've tried using variations of grep, but have been unsuccessful in applying it when also matching the state and year columns. There are also other columns that I'd be pulling in the merge, but these are the relevant ones to be joined on.