K-Similar Strings
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'}
class Solution {
public int kSimilarity(String A, String B) {
char[] strB = B.toCharArray();
Queue<String> q = new LinkedList<>();
q.add(A);
int count = 0;
while (q.size() != 0) {
int size = q.size();
while (size-- > 0) {
char[] node = q.poll().toCharArray();
int i = 0;
while (i < strB.length && node[i] == strB[i])
i++;
// If found match
if (i == strB.length)
return count;
for (int j = i + 1; j < node.length; j++) {
if (node[j] == strB[i]) {
swap(node, i, j);
q.add(new String(node));
swap(node, i, j);
}
}
}
count++;
}
return -1;
}
public void swap(char[] str, int i, int j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
}
}
Last updated