【原】精选算法题(4)——字符串比较

翟天保的图书馆 2023-08-01 发布于上海

展开全文

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

题目描述：

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

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

解题思路：

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

取idx1和idx2作为滑动窗口起点。以字符串1为基准，遍历字符串2寻找相同的字符。
当两个字符一致时，判断下j和idx2的大小情况，如果j大且i和idx1一致，说明字符串2相同字符前面有一段字符是多出的。之后，将idx1加1，再使idx2等于j+1，这样可以使两个字符串的滑动窗口从相同字符后的一个位置开始。
如果i大于idx1，且j和idx2一致，同理，说明字符串1相同字符前面缺少了一段字符。之后，idx2加1，idx1等于i+1即可。
如果i大于idx1，j也大于idx2，说明两个字符串相同字符前，各有一段不相同字符，即匹配错误。
若上述三个条件都不满足，那就说明碰到了连续相同字符串。令idx1和idx2都加1，跳过即可。
如果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;
}