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

简介: 精选算法题(4)——字符串比较

题目描述:

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


两个字符串比较,如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;
}

测试代码:

相关文章
|
2月前
|
算法
【优选算法】—— 字符串匹配算法
【优选算法】—— 字符串匹配算法
|
3月前
|
人工智能 算法 测试技术
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
|
4月前
|
算法 测试技术 C#
【动态规划】【字符串】C++算法:正则表达式匹配
【动态规划】【字符串】C++算法:正则表达式匹配
|
4月前
|
算法 Java C++
试题 算法训练 最长字符串
试题 算法训练 最长字符串
11 0
|
4月前
|
算法 C++ 索引
leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)
leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)
32 0
|
3月前
|
机器学习/深度学习 算法 C语言
【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“
【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“
74 0
|
22天前
|
算法
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
24 1
|
1月前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
2月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
24 0
|
3月前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串