problem:https://leetcode.com/problems/k-similar-strings/
看到题目描述中的最短交换次数，差不多可以确定使用宽度优先搜索。由于题目中字符串长度限定为20以下，所以使用深度优先搜索应该也是可行的。
主要的难点在于限定搜索范围。如果不限制搜索范围的话，对于长度为N字符串，可能存在的交换一次得到的字符串有 N * (N - 1) 种。即使我们使用visit标记排除了已经访问过的字符串，最终加入到队列中的字符串的数量也是可观的，因此我们要尽可能选择更加接近结果的字符串。
那么，应该如何定义“离结果更近”这一行为呢？我们可以认为，如果经过一次交换，字符串A和B匹配的字符至少多了一个，那么它更加接近结果。这样可以保证我们并不是漫无目的的搜索结果，而是有一定方向性的。
为了快速找到匹配的字符，对于保持不变的字符串B，可以做一次预处理，记录每个字符出现的位置。
class Solution { public: int kSimilarity(string A, string B) { queue<string> q; q.push(A); unordered_set<string> visit; visit.insert(A); int res = 0; vector<vector<int>> pos(6); for(int i = 0;i < B.size();i++) { pos[B[i] - ‘a‘].push_back(i); } while(!q.empty()) { res++; int size = q.size(); while(size--) { string cur = q.front(); q.pop(); for(int i = 0; i < cur.size(); i++) { if(cur[i] != B[i]) { auto& p = pos[cur[i] - ‘a‘]; for(int j = 0; j < p.size();j++) { string& next = cur; if(cur[p[j]] == B[p[j]]) continue; swap(next[i], next[p[j]]); if(visit.find(next) == visit.end()) { if(next == B) { return res; } visit.insert(next); q.push(next); } swap(next[i], next[p[j]]); } break; } } } } return 0; } };
[宽度优先搜索] leetcode 854 K-Similar Strings
原文：https://www.cnblogs.com/fish1996/p/11260826.html