# 854. 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. `1 <= A.length == B.length <= 20`
2. `A` and `B` contain only lowercase letters from the set `{'a', 'b', 'c', 'd', 'e', 'f'}`

``````class Solution {
public:
int kSimilarity(string A, string B) {
int res = 0, n = A.size();
queue<string> q{{A}};
unordered_set<string> visited{{A}};
while (!q.empty()) {
for (int k = q.size(); k > 0; --k) {
string cur = q.front(); q.pop();
if (cur == B) return res;
int i = 0;
while (i < n && cur[i] == B[i]) ++i;
for (int j = i + 1; j < n; ++j) {
if (cur[j] == B[j] || cur[j] != B[i]) continue;
swap(cur[i], cur[j]);
if (!visited.count(cur)) {
visited.insert(cur);
q.push(cur);
}
swap(cur[i], cur[j]);
}
}
++res;
}
return -1;
}
};
``````

``````class Solution {
public:
int kSimilarity(string A, string B) {
unordered_map<string, int> memo;
return helper(A, B, 0, memo);
}
int helper(string cur, string B, int i, unordered_map<string, int>& memo) {
if (cur == B) return 0;
if (memo.count(cur)) return memo[cur];
int res = INT_MAX, n = cur.size();
while (i < n && cur[i] == B[i]) ++i;
for (int j = i + 1; j < n; ++j) {
if (cur[j] == B[j] || cur[j] != B[i]) continue;
swap(cur[i], cur[j]);
int next = helper(cur, B, i + 1, memo);
if (next != INT_MAX) {
res = min(res, next + 1);
}
swap(cur[i], cur[j]);
}
return memo[cur] = res;
}
};
``````

``````class Solution {
public:
int kSimilarity(string A, string B) {
int n = A.size(), res = n - 1;
for (int i = 0; i < n; ++i) {
if (A[i] == B[i]) continue;
vector<int> matches;
for (int j = i + 1; j < n; ++j) {
if (A[j] == B[j] || A[j] != B[i]) continue;
matches.push_back(j);
if (A[i] != B[j]) continue;
swap(A[i], A[j]);
return 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1));
}
for (int j : matches) {
swap(A[i], A[j]);
res = min(res, 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1)));
swap(A[i], A[j]);
}
return res;
}
return 0;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/854

Couples Holding Hands

https://leetcode.com/problems/k-similar-strings/

https://leetcode.com/problems/k-similar-strings/discuss/140299/C%2B%2B-6ms-Solution

https://leetcode.com/problems/k-similar-strings/discuss/139872/Java-Backtracking-with-Memorization

https://leetcode.com/problems/k-similar-strings/discuss/140099/JAVA-BFS-32-ms-cleanconciseexplanationwhatever

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation