C++如何判断字符串包含另一字符串的字符（允许中间存在重复字符）

核心逻辑 #

你之前的思路问题在于：仅判断typed包含name所有字符是不够的，必须同时满足两个条件：

1. 字符出现的顺序完全和name一致
2. name中每一段连续相同字符的长度，不能超过typed对应位置连续相同字符的长度

具体实现步骤 #

• 定义两个下标指针i、j，分别指向name和typed的起始位置
• 循环遍历两个字符串，每次处理一组连续相同的字符块：
  1. 若当前j已经走到typed末尾但i还没走完name，直接返回false
  2. 若当前name[i]和typed[j]不相等，直接返回false
  3. 统计name中从i开始连续和name[i]相同的字符数量cntName，指针i后移到下一个不同字符的位置
  4. 统计typed中从j开始连续和typed[j]相同的字符数量cntTyped，指针j后移到下一个不同字符的位置
  5. 如果cntTyped < cntName，说明typed对应位置的连续字符数不够，返回false
• 遍历结束后，确认name已经全部匹配完成，直接返回true

完整可运行代码 #

#include <string>
using namespace std;

bool isLongPressedName(string name, string typed) {
    int n = name.size(), m = typed.size();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (name[i] != typed[j]) return false;
        // 统计name当前连续字符数
        char cur = name[i];
        int cntN = 0;
        while (i < n && name[i] == cur) {
            cntN++;
            i++;
        }
        // 统计typed当前连续字符数
        int cntT = 0;
        while (j < m && typed[j] == cur) {
            cntT++;
            j++;
        }
        if (cntT < cntN) return false;
    }
    // 必须name全部匹配完，typed剩余字符已经在前面的校验中确认和最后一个字符一致
    return i == n;
}

样例验证 #

我们用你给出的第二个反例验证：
输入name = "saeed"，typed = "ssaaedd"

• 第一组字符s：cntN=1，cntT=2，满足条件
• 第二组字符a：cntN=1，cntT=2，满足条件
• 第三组字符e：cntN=2，cntT=1，cntT < cntN，直接返回false，和样例输出一致

内容的提问来源于stack exchange，提问作者stiwenparker