在 C++ 中查找 K 相似字符串的 K 值的程序
假设我们有两个字符串s和t。当我们可以将s中两个字母的位置恰好交换K次以便结果字符串是t时，这两个字符串是K相似的。我们有两个字谜s和t，我们必须找到最小的K，其中s和t是K相似的。
因此，如果输入类似于s="abc",t="bac"，那么输出将为1。
示例
让我们看下面的实现来更好地理解
#includeusing namespace std; class Solution { public: int kSimilarity(string A, string B) { if (A == B) return 0; unordered_set visited; visited.insert(A); queue q; q.push(A); for (int lvl = 1; !q.empty(); lvl++) { int sz = q.size(); while (sz--) { string curr = q.front(); q.pop(); int i = 0; while (i < curr.size() && curr[i] == B[i]) i++; for (int j = i + 1; j < curr.size(); j++) { if (curr[i] == curr[j]) continue; if (curr[j] != B[i]) continue; if (curr[j] == B[j]) continue; swapp(curr, i, j); if (curr == B) return lvl; if (!visited.count(curr)) { visited.insert(curr); q.push(curr); } swapp(curr, i, j); } } } return -1; } void swapp(string &s, int i, int j) { char x = s[i]; char y = s[j]; s[i] = y; s[j] = x; } }; main(){ Solution ob; cout << (ob.kSimilarity("abc", "bac")); }
输入
"abc", "bac"输出结果
1