精选算法题(4)——字符串比较_比较字符串,abcdefg和25abdfg

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

好久没做题目了，近期刷抖音碰到一个题目，乍一看不是很难，但是手生了，就写个玩玩，大家轻喷。

两个字符串比较，如abcdefg和25abdfxx，返回：位置0多出:25；位置2缺少:c；位置4缺少:e；位置6错误，应为g。

解题思路：

我看很多人说双指针法、动态规划能解，我暂时没想那么多，就用了简单的双循环+滑动窗口。

1. 取idx1和idx2作为滑动窗口起点。以字符串1为基准，遍历字符串2寻找相同的字符。
2. 当两个字符一致时，判断下j和idx2的大小情况，如果j大且i和idx1一致，说明字符串2相同字符前面有一段字符是多出的。之后，将idx1加1，再使idx2等于j+1，这样可以使两个字符串的滑动窗口从相同字符后的一个位置开始。
3. 如果i大于idx1，且j和idx2一致，同理，说明字符串1相同字符前面缺少了一段字符。之后，idx2加1，idx1等于i+1即可。
4. 如果i大于idx1，j也大于idx2，说明两个字符串相同字符前，各有一段不相同字符，即匹配错误。
5. 若上述三个条件都不满足，那就说明碰到了连续相同字符串。令idx1和idx2都加1，跳过即可。
6. 如果i走到最后都没找到匹配对象，则从idx1到字符串1结尾所有字符都匹配失败了。

测试代码：

#include <iostream>
#include <string>
using namespace std;
 
void compareStrings(std::string str1, std::string str2) {
	int len1 = str1.length();
	int len2 = str2.length();
	
	int idx1 = 0;
	int idx2 = 0;
	for (int i = 0; i < len1; ++i) {
		for (int j = idx2; j < len2; ++j) {
			if (str1[i] == str2[j]) {
				if (j > idx2 && i == idx1) {
					cout << "位置" << i << "多出：" << str2.substr(idx2, j - idx2) << endl;
					idx1++;
					idx2 = j + 1;
				}
				else if (i > idx1 && j == idx2) {
					cout << "位置" << idx1 << "缺少：" << str1.substr(idx1, i - idx1) << endl;
					idx1 = i + 1;
					idx2++;
				}
				else if (i > idx1 && j > idx2) {
					cout << "位置" << idx1 << "错误，应为：" << str1.substr(idx1, i - idx1) << endl;
					idx1 = i + 1;
					idx2= j + 1;
				}
				else{
					idx1++;
					idx2++;
				}
				break;
			}			
		}
		if (i == (len1 - 1) && (idx1 < len1)) {
			cout << "位置" << idx1 << "错误，应为：" << str1.substr(idx1, i - idx1 + 1) << endl;
		}
	}
}
 
int main() {
	std::string str1 = "abcdefg";
	std::string str2 = "25abdfxx";
	cout << "字符串1：" << str1 << endl;
	cout << "字符串2：" << str2 << endl;
	compareStrings(str1, str2);
	return 0;
}
 

测试结果：

字符串如题目要求时，结果如下，可以发现是满足的。

加几个字符再试试，依然可行。

中间内容再打乱一些，暂无问题。

多几个重复字符，按照我的逻辑，输出结果是对的，但不知道题目是不是这意思。

       如果代码有什么需要改进的或者有什么bug，欢迎评论留言，我会及时更正以免误导他人~

       如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！

---

       有朋友提出了问题，所以我对算法进行了改进。

1. 基于动态规划表获取两个字符串的最长非连续重复子串。
2. 用子串作为参照物，逐一字符遍历。取两个字符串在该字符前的字符串比较，根据不同情况做出不同反馈，具体参见代码和注释。

测试代码：

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
// 获取最长重复子串（可不连续）
string getSubString(std::string str1, std::string str2) {
	int len1 = int(str1.length());
	int len2 = int(str2.length());
 
	// 动态规划
	vector<vector<int>> m(len1 + 1, vector<int>(len2 + 1, 0));
	vector<vector<string>> s(len1 + 1, vector<string>(len2 + 1, ""));
	for (int i = 1; i <= len1; ++i){
		for (int j = 1; j <= len2; ++j){
			if (str1[i - 1] == str2[j - 1]){
				m[i][j] = m[i - 1][j - 1] + 1;
				s[i][j] = s[i - 1][j - 1] + str1[i - 1];
			}
			else{
				if (m[i - 1][j] > m[i][j - 1]){
					m[i][j] = m[i - 1][j];
					s[i][j] = s[i - 1][j];
				}
				else{
					m[i][j] = m[i][j - 1];
					s[i][j] = s[i][j - 1];
				}
			}
		}
	}
	return s[len1][len2];
}
 
// 比较字符串
void compareString(string str1, string str2, string substr) {
	int len1 = int(str1.length());
	int len2 = int(str2.length());
	int len3 = int(substr.length());
 
	// 以重复子串字符遍历
	// 若截止到第一个重复字符，t1空，t2有，那就是多出；t1有，t2空，那就是缺少。
	// 两个都空说明连续重复字符；若两个都不空，则说明错误。
	// 缺少和错误的状态按位置挨个字符输出。
	int idx1 = 0;
	int idx2 = 0;
	for (int i = 0; i < len3; ++i) {
		string t1, t2;
		int idx3 = idx1;
		int idx4 = idx2;
		// t1为字符串1在当前重复字符前的字符串
		for (int m = idx1; m < len1; ++m) {
			if (str1[m] == substr[i]) {
				t1 = str1.substr(idx1, m - idx1);
				idx1 = m + 1;
				break;
			}
		}
		// t2为字符串2在当前重复字符前的字符串
		for (int n = idx2; n < len2; ++n) {
			if (str2[n] == substr[i]) {
				t2 = str2.substr(idx2, n - idx2);
				idx2 = n + 1;
				break;
			}
		}
		// 根据不同情况处理
		if (t1 == "" && t2 != "") {
			cout << "位置" << idx3 << "多出：" << t2 << endl;
		}
		else if (t1 != "" && t2 == "") {
			while (t1 != "") {
				cout << "位置" << idx3 << "缺少：" << t1[0] << endl;
				idx3++;
				t1 = t1.substr(1, t1.size() - 1);
			}
		}
		else if (t1 == "" && t2 == "") {
		}
		else {
			while (t1 != "") {
				cout << "位置" << idx3 << "错误，应为：" << t1[0] << endl;
				idx3++;
				t1 = t1.substr(1, t1.size() - 1);
			}
		}
	}
	// 对尾巴数据处理
	if (idx1 < len1) {
		string tail = str1.substr(idx1, len1 - idx1);
		while (tail != "") {
			cout << "位置" << idx1 << "错误，应为：" << tail[0] << endl;
			idx1++;
			tail = tail.substr(1, 1);
		}
	}
}
 
int main() {
	std::string str1 = "1abcdefui";
	std::string str2 = "abxcegfui";
	cout << "字符串1：" << str1 << endl;
	cout << "字符串2：" << str2 << endl;
 
	// 获取最长重复子串（可不连续）
	string substr = getSubString(str1, str2);
	cout << "substring:" << substr << endl;
 
	// 比较字符串
	compareString(str1, str2, substr);
 
	system("pause");
	return 0;
}

测试代码：