【广度优先搜索深度优先搜索图论】854. 相似度为 K 的字符串

本文涉及知识点

广度优先搜索深度优先搜索图论

图论知识汇总
深度优先搜索汇总
C++BFS算法

LeetCode 854. 相似度为 K 的字符串

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
示例 1：
输入：s1 = “ab”, s2 = “ba”
输出：1
示例 2：
输入：s1 = “abc”, s2 = “bca”
输出：2
提示：
1 <= s1.length <= 20
s2.length == s1.length
s1 和 s2 只包含集合 {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’} 中的小写字母
s2 是 s1 的一个字母异位词

广度优先搜索

本题没出好：不好计算复杂度，所以无法估计是否超时。
哈希映射visit记录那些字符串已经处理。
que记录待处理字符串。
两层循环：一，操作的步骤。二，枚举que中元素。一层循环一可以。
由于是字母异位词，所以一定能计算相似度。
处理每个字符串的逻辑：
如果和s2相等，直接返回。
如果不相等，只交换第一个不等。即cur[i] != s2[i] ,且i最小。令cur[i]和cur[j]交换，则 s2[i] == cur[j] ，缺 cur[j] != s2[j]。用到了以下两个性质：
性质一，如果已经相等，则无需交换。
性质二，第一次交换，只需要考虑最小的i。
下面来用图论（方法一）来证明：
如果s1[i] != s2[i]，则增加有向边s1[i] $\rightarrow$ s2[2] ,整个交换过程一定是若干环。本题 $\iff$ y = 边数 - 环数。 s1[i] == s2[i] ,则是自环，自环的边数和环数都为1，有没有自环，不影响y。性质一得证。由于交换是若干环， $\forall$ 环，从任意起点开始的结果都一样。

本题 $\iff$ y = 边数 - 环数的证明过程太复杂，本人不会，以后会了补上。

代码

核心代码

class Solution {
public:int kSimilarity(string s1, string s2) {set<string> vis;queue<string> que;que.emplace(s1);for (int step = 0; ; step++) {queue<string> curQue;auto Add = [&](const string& s) {if (vis.count(s)) { return; }vis.emplace(s);curQue.emplace(s);};while (que.size()) {const auto cur = que.front();que.pop();if (cur == s2) { return step; }int i = 0;for (; cur[i] == s2[i]; i++);for (int j = 0; j < cur.length(); j++) {if (cur[j] == s2[i]) {auto tmp = cur;std::swap(tmp[i], tmp[j]);Add(tmp);}}}que.swap(curQue);}return -1;}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string s1,  s2;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod1){s1 = "ab", s2 = "ba";auto res = Solution().kSimilarity(s1, s2);AssertEx(1, res);}TEST_METHOD(TestMethod2){s1 = "abc", s2 = "bca";auto res = Solution().kSimilarity(s1, s2);AssertEx(2, res);}TEST_METHOD(TestMethod3){s1 = "baaabaabbbabbbabaaab", s2 = "babbbbbaabaabaaaabba";auto res = Solution().kSimilarity(s1, s2);AssertEx(6, res);}TEST_METHOD(TestMethod4){s1 = "abccaacceecdeea", s2 = "bcaacceeccdeaae";auto res = Solution().kSimilarity(s1, s2);AssertEx(9, res);}};
}

性能优化

不用把整个字符串入队，相同的前缀省略。

class Solution {
public:int kSimilarity(string s1, string s2) {set<string> vis;queue<pair<string,int>> que;que.emplace(s1,0);for (int step = 0; ; step++) {queue<pair<string, int>> curQue;auto Add = [&](const string& s,int begin) {if (vis.count(s)) { return; }vis.emplace(s);curQue.emplace(s,begin);};while (que.size()) {const auto [cur,begin] = que.front();que.pop();auto tmpS2 = s2.substr(begin);if (cur == tmpS2) { return step; }int i = 0;for (; cur[i] == tmpS2[i]; i++);for (int j = 0; j < cur.length(); j++) {if (cur[j] == tmpS2[i]) {auto tmp = cur;std::swap(tmp[i], tmp[j]);Add(tmp.substr(i+1),begin+i+1);}}}que.swap(curQue);}return -1;}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛