• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jun 16th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import collections
2.
3. class Solution:
4.
5.     def find_first_mismatch(self, A, B):
6.         for i in range(len(A)):
7.             if A[i] != B[i]:
8.                 return i
9.
10.     def find_candidates(self, A, B, mismatch):
11.         for i in range(mismatch + 1, len(A)):
12.             if A[i] != B[i] and A[i] == B[mismatch]:
13.                 yield Solution.swap(A, mismatch, i)
14.
15.     def swap(A, i, j):
16.         chars = list(A)
17.         chars[i], chars[j] = chars[j], chars[i]
18.         return "".join(chars)
19.
20.     def k_similarity(self, A, B):
21.         """
22.         :type A: str
23.         :type B: str
24.         :rtype: int
25.         """
26.         q = collections.deque([A])
27.         distance = 0
28.         seen = set([A])
29.         while q:
30.             for _ in range(len(q)):
31.                 current = q.pop()
32.                 if current == B:
33.                     return distance
34.                 mismatch = self.find_first_mismatch(current, B)
35.                 for candidate in self.find_candidates(current, B, mismatch):
36.                     if candidate not in seen:
38.                         q.appendleft(candidate)
39.             distance += 1
40.
41. Input: A = "ab", B = "ba"
42. Output: 1
43.
44. Input: A = "abc", B = "bca"
45. Output: 2
46.
47. Input: A = "abac", B = "baca"
48. Output: 2
49.
50. Input: A = "aabc", B = "abca"
51. Output: 2
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top