刀大师经典题

DoorDash obtains restaurant data from various sources which have varying quality. Thesesources often have duplicate merchants with minor typos in their names. The assignment is to
create a list of unique restaurants across various sources ignoring the errors before onboarding
them.
Definition: Similar restaurants
Two restaurants R1 and R2 are similar if we can swap a maximum of two letters (in different
positions) of R1, so that it equals R2.
For example, source one may have a restaurant named "omega grill" while another source may
have the same restaurant as "omgea grill".
For example, "biryani" and "briyani" are similar (swapping at positions 1 and 2). "biryani" is not
similar to following, "biryeni" (no e to swap with), "briynai"(Needs 2 swap)
For a given restaurant name, find and return all the similar restaurant names in the list.
Implement the function below:
public List findSimilarRestaurants(String name, String[] list) {}
#Tests
input = "hotpot"
list = ["hottop", "hotopt", "hotpit", "httoop", "hptoot"]

1. # Online Python compiler (interpreter) to run Python online.
   
2. # Write Python 3 code in this online editor and run it.
   
3. from typing import List   
   
4. def get_sign(s: str) -> str:
   
5.     cts = [0] * 26
   
6.     for c in s:
   
7.         cts[ord(c) - ord('a')] += 1
   
8.     return cts
   
9. 
   
10. def find_k_anagram(s: str, candis: List[str], k: int) -> List[str]:
    
11.     anag = [candi for candi in candis if get_sign(candi) == get_sign(s)]
    
12.     result = list()
    
13.    
    
14.     for i in range(len(anag)):
    
15.         pairs = set()
    
16.         count = 0
    
17.         for cs, ci in zip(anag[i], s):
    
18.             if cs != ci:
    
19.                 if (cs, ci) in pairs:
    
20.                     pairs.remove((cs, ci))
    
21.                     count += 1
    
22.                 else:
    
23.                     pairs.add((ci, cs))
    
24.         if count > k: continue
    
25.         count = count + len(pairs) - 1
    
26.         if count <= k: result.append(anag[i])
    
27.     return result            
    
28. 
    
29. print(find_k_anagram("hotpot", ["hottop", "hotopt", "hotpit", "httoop", "hptoot"],2))

复制代码