LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用两个指针 i 和 j 来标记 s 和 p 的当前位置，依次检查 s[i] 与 p[j] 的匹配情况，匹配过程如果出现不匹配的情况则 s 和 p 不能匹配
• 匹配过程中有一个特殊情况，p[j] 为 * 时可以匹配任意字符串，如果使用了 * 之后再不匹配，则应当回退到使用上一个 * 之前的状态。用两个标记 markS 和 markP 来记录遇到 * 时的 i 和 j，之后 i 和 j 使用此标记即可回退到此状态

s abcdef
p ab*f
i = 0 j = 0

s a
p a
s[0] 匹配 p[0] => i = 1 j = 1

s ab
p ab
s[1] 匹配 p[1] => i = 2 j = 2

s abc
p ab*
p[2]为* => 标记 i 和 j，并让 j 加 1 => markS = 2 markP = 2 => i = 2 j = 3

s abc
p ab*f
s[2] 不匹配 p[3] => 回退并进入下一位置 => i = 3 j = 3 => 标记i => markS = 3 markP = 2

s abcd
p ab*f
s[3] 不匹配 p[3] => 回退并进入下一位置 => i = 4 j = 3 => 标记i => markS = 4 markP = 2

s abcde
p ab*f
s[4] 不匹配 p[3] => 回退并进入下一位置 => i = 5 j = 3 => 标记i => markS = 5 markP = 2

s abcdef
p ab*f
s[5] 匹配 p[3] => i = 6 j = 4 => i 超出 s 长度，结束匹配 => 检查 j 等于 p 长度 => 匹配成功

• 解法如下

class Solution {
 public:
  bool isMatch(string s, string p) {
    int i = 0;
    int j = 0;
    int markS = -1;        // 未使用过，先设置为-1
    int markP = -1;        // 未使用过，先设置为-1
    while (i < size(s)) {  // 遍历 s[i]
      if (j < size(p) && (s[i] == p[j] || p[j] == '?')) {
        ++i;
        ++j;
      } else if (j < size(p) && p[j] == '*') {
        markS = i;
        markP = j;
        ++j;  // 标记位置后，不移动 s
        // 让 s 继续匹配 p 的下一位置，让 * 匹配尽可能少的元素
        // 如果下次不匹配则回退状态，再让 s 前进一步，* 匹配的元素数增加一个
      } else if (markP != -1) {  // s[i] 不匹配 p[j]，但上一次使用了 *
        // 回退到上一次状态
        i = ++markS;  // i 回退到 markS 或者 markS + 1 均可
        // 但 markS 必须标记下一位置，否则两个标记位置都没变化，会进入死循环
        j = markP + 1;  // 也可以写为 j = markP
        // 不过 p[markP] 就是 *，下次会进入上一条逻辑分支
        // 因此这里可以直接让 j = markP + 1，把下一步的逻辑并入此处
      } else {  // 不匹配且未使用过 *，没有可回退的状态，匹配失败
        return false;
      }
    }
    while (j < size(p) && p[j] == '*') {
      ++j;  // 易忽略此状况，可能还有多余的 *
    }
    return j == size(p);
  }
};