# 854. K-Similar Strings    • Time: $O(n^2k)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public: int kSimilarity(string s1, string s2) { int ans = 0; queue q{{s1}}; unordered_set seen{{s1}}; while (!q.empty()) { for (int sz = q.size(); sz > 0; --sz) { string curr = q.front(); q.pop(); if (curr == s2) return ans; for (const string& child : getChildren(curr, s2)) { if (seen.count(child)) continue; q.push(child); seen.insert(child); } } ++ans; } return -1; } private: vector getChildren(string& curr, const string& target) { vector children; int i = 0; // the first index s.t. curr[i] != target[i] while (curr[i] == target[i]) ++i; for (int j = i + 1; j < curr.length(); ++j) if (curr[j] == target[i]) { swap(curr[i], curr[j]); children.push_back(curr); swap(curr[i], curr[j]); } return children; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class Solution { public int kSimilarity(String s1, String s2) { int ans = 0; Queue q = new ArrayDeque<>(Arrays.asList(s1)); Set seen = new HashSet<>(Arrays.asList(s1)); while (!q.isEmpty()) { for (int sz = q.size(); sz > 0; --sz) { final String curr = q.poll(); if (curr.equals(s2)) return ans; for (final String child : getChildren(curr, s2)) { if (seen.contains(child)) continue; q.offer(child); seen.add(child); } } ++ans; } return -1; } private List getChildren(final String curr, final String target) { List children = new ArrayList<>(); char[] charArray = curr.toCharArray(); int i = 0; // the first index s.t. curr.charAt(i) != target.charAt(i) while (curr.charAt(i) == target.charAt(i)) ++i; for (int j = i + 1; j < charArray.length; ++j) if (curr.charAt(j) == target.charAt(i)) { swap(charArray, i, j); children.add(String.valueOf(charArray)); swap(charArray, i, j); } return children; } private void swap(char[] charArray, int i, int j) { final char temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution: def kSimilarity(self, s1: str, s2: str) -> int: ans = 0 q = collections.deque([s1]) seen = {s1} while q: for _ in range(len(q)): curr = q.popleft() if curr == s2: return ans for child in self._getChildren(curr, s2): if child in seen: continue q.append(child) seen.add(child) ans += 1 return -1 def _getChildren(self, curr: str, target: str) -> List[str]: children = [] s = list(curr) i = 0 # the first index s.t. curr[i] != target[i] while curr[i] == target[i]: i += 1 for j in range(i + 1, len(s)): if s[j] == target[i]: s[i], s[j] = s[j], s[i] children.append(''.join(s)) s[i], s[j] = s[j], s[i] return children