Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/854.html
854. K-Similar Strings
Level
Hard
Description
Strings A
and B
are K
-similar (for some non-negative integer K
) if we can swap the positions of two letters in A
exactly K
times so that the resulting string equals B
.
Given two anagrams A
and B
, return the smallest K
for which A
and B
are K
-similar.
Example 1:
Input: A = “ab”, B = “ba”
Output: 1
Example 2:
Input: A = “abc”, B = “bca”
Output: 2
Example 3:
Input: A = “abac”, B = “baca”
Output: 2
Example 4:
Input: A = “aabc”, B = “abca”
Output: 2
Note:
1 <= A.length == B.length <= 20
A
andB
contain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}
Solution
If A
and B
are the same, return 0.
Loop over A
and B
and only keep the letters that are different in the two strings. For example, if A = "aabc"
and B = "abca"
, since the first letter 'a'
is the same in A
and B
, it is not kept, so A
and B
become "abc"
and "bca"
respectively. After removing the same letters, all the letters need to be swapped, which can reduce the search space.
Then do breadth first search starting from A
. For each string visited, which is str
, obtain the first index where the letter in the string is different to the letter in B
, which is startIndex
. Then loop over all indices after startIndex
and swap the letters at index i
and index startIndex
only if str.charAt(i) == B.charAt(startIndex)
. After swapping, add the new string to the queue for further search. Also maintain the number of swaps so far.
If at one step, the string equals B
, then return the number of swaps.
-
class Solution { public int kSimilarity(String A, String B) { if (A.equals(B)) return 0; int length = A.length(); StringBuffer sbA = new StringBuffer(); StringBuffer sbB = new StringBuffer(); for (int i = 0; i < length; i++) { char cA = A.charAt(i), cB = B.charAt(i); if (cA != cB) { sbA.append(cA); sbB.append(cB); } } String strA = sbA.toString(); String strB = sbB.toString(); int swaps = 0; Set<String> set = new HashSet<String>(); Queue<String> queue = new LinkedList<String>(); queue.offer(strA); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String str = queue.poll(); if (str.equals(strB)) return swaps; List<String> neighbors = getNeighbors(str, strB); for (String neighbor : neighbors) { if (set.add(neighbor)) queue.offer(neighbor); } } swaps++; } return -1; } public List<String> getNeighbors(String str, String target) { int length = str.length(); int startIndex = -1; for (int i = 0; i < length; i++) { if (str.charAt(i) != target.charAt(i)) { startIndex = i; break; } } List<String> neighbors = new ArrayList<String>(); if (startIndex < 0) return neighbors; char[] array = str.toCharArray(); char targetC = target.charAt(startIndex); for (int i = startIndex + 1; i < length; i++) { if (array[i] == targetC) { swap(array, startIndex, i); neighbors.add(new String(array)); swap(array, startIndex, i); } } return neighbors; } public void swap(char[] array, int index1, int index2) { char temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }
-
// OJ: https://leetcode.com/problems/k-similar-strings/ // Time: O(?) // Space: O(?) // Ref: https://leetcode.com/problems/k-similar-strings/discuss/151500/Logical-Thinking-with-Clear-Java-Code class Solution { public: int kSimilarity(string s, string t) { queue<string> q{ {s} }; unordered_set<string> seen{ {s} }; int step = 0; while (q.size()) { int cnt = q.size(); while (cnt--) { auto u = q.front(); q.pop(); if (u == t) return step; int i = 0; // Get all possible neighbor strings while (i < s.size() && u[i] == t[i]) ++i; // find the first index that u[i] != t[i] for (int j = i + 1; j < s.size(); ++j) { // find a good swap index j such that u[j] == t[i] if (u[j] == t[i]) { swap(u[i], u[j]); if (seen.count(u) == 0) { seen.insert(u); q.push(u); } swap(u[i], u[j]); } } } ++step; } return -1; } };
-
class Solution: def kSimilarity(self, s1: str, s2: str) -> int: def next(s): i = 0 while s[i] == s2[i]: i += 1 res = [] for j in range(i + 1, n): if s[j] == s2[i] and s[j] != s2[j]: res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :]) return res q = deque([s1]) vis = {s1} ans, n = 0, len(s1) while 1: for _ in range(len(q)): s = q.popleft() if s == s2: return ans for nxt in next(s): if nxt not in vis: vis.add(nxt) q.append(nxt) ans += 1
-
func kSimilarity(s1 string, s2 string) int { next := func(s string) []string { i := 0 res := []string{} for ; s[i] == s2[i]; i++ { } for j := i + 1; j < len(s1); j++ { if s[j] == s2[i] && s[j] != s2[j] { res = append(res, s[:i]+string(s[j])+s[i+1:j]+string(s[i])+s[j+1:]) } } return res } q := []string{s1} vis := map[string]bool{s1: true} ans := 0 for { for i := len(q); i > 0; i-- { s := q[0] q = q[1:] if s == s2 { return ans } for _, nxt := range next(s) { if !vis[nxt] { vis[nxt] = true q = append(q, nxt) } } } ans++ } }