C++ 检查两个字符串内容效率

Question

假设我有以下两个字符串:

string s1 =//一些字符串

string s2 =//一些字符串

如何有效地检查 s1 与 s2 是否仅相差 1 个字母？ (如果 s1 长度 == s2 长度)

如何有效地检查 s1 与 s2 是否有 1 个插入字母的不同？

如何有效地检查 s1 与 s2 是否有 1 个字母删除的差异？

如何有效地检查s1的字母是否可以连续配对并交换到s12的相等内容？

Answer 1

对于第一个问题，考虑迭代每个字母对，并计算不同的字母对。如果您的总计数等于 1，则条件满足。 (例如，使用 for(int i = 0; i < s1.length(); ++i) )

对于第二个问题，首先检查是否s1.length() == s2.length() + 1 .然后，遍历字母对，直到找到第一对不匹配的字母。然后，将 s1 的索引增加 1，这样您就可以比较 s1[i+1]。至 s2[i] .如果以这种方式选择的其余对匹配，则我们知道 s1 是通过插入单个字母从 s2 形成的。

对于第三个问题，我们可以做同样的事情，但交换 s1 和 s2。

对于最后一个问题，考虑计算每个字符在两个字符串中的出现次数。如果它们每个字符的计数相同，那么您将能够进行成对交换以从另一个交换(result from group theory——“每个排列都可以表示为换位的乘积”)。

所有这些操作都是 O(n) 的，这对于字符串比较来说已经是最好的了。