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:
  37.                         seen.add(candidate)
  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. OK, I Understand
 
Top