用 dfs 暴力搜索即可通过本题。即如下代码：
class Solution { public: int kSimilarity(string s1, string s2) { solve(s1, s2, 0, 0); return ret; } private: int ret = INT_MAX; void solve(string &s1, string &s2, int i, int cnt) { if(i == s2.size()) { ret = min(ret, cnt); return ; } if(s1[i] == s2[i]) solve(s1, s2, i + 1, cnt); else { for(int j = i + 1; j < s2.size(); ++ j) { if(s2[j] != s1[i]) continue; swap(s2[i], s2[j]); solve(s1, s2, i + 1, cnt + 1); swap(s2[i], s2[j]); } } } };
可以剪枝进行优化：
在 dfs 中的 for 循环里面，如果交换后 s2[j] == s1[j]，那么当前交换肯定是最优的，可以在末尾进行 break..其次，如果 cnt >= ret 了，也是可以直接 return 的
class Solution { public: int kSimilarity(const string &s1, string s2) { solve(s1, s2, 0, 0); return ret; } private: int ret = INT_MAX; void solve(const string &s1, string &s2, int i, int cnt) { if (cnt >= ret) return; if (i == s2.size()) { ret = min(ret, cnt); return; } if (s1[i] == s2[i]) { solve(s1, s2, i + 1, cnt); return; } for (int j = i + 1; j < s2.size(); ++j) { if (s2[j] != s1[i] || s2[j] == s1[j]) continue; swap(s2[i], s2[j]); bool flag = s1[j] == s2[j]; solve(s1, s2, i + 1, cnt + 1); swap(s2[i], s2[j]); if(flag) break; // 当前肯定是一次最优, 没必要继续 for 求解 } } };
剪枝与未剪枝的时间：