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

• 动态规划，用二维数组 dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
• 初始状态下，空字符串肯定匹配。此外，如果 p[i] 为 *，则 p[i - 1]p[i] 可以匹配空字符串，此时如果 p[i - 1] 之前的子串能匹配空字符串，则连上 p[i - 1]p[i] 也能匹配空字符串

dp[0][0] = true;

for (int i = 2; i < size(dp[0]); i += 2) {
  if (p[i - 1] != '*') {
    break;
  }
  dp[0][i] = true;
}

• 这样就完成了初始解的构造，接着考虑 s[0]...s[i] 和 p[0]...p[j] 的匹配情况，即 dp[i + 1][j + 1]
• 第一种情况，如果 s[i] 匹配 p[j]，则 s[0]...s[i]、p[0]...p[j] 的匹配情况与 s[0]...s[i - 1]、p[0]...p[j - 1] 相同

s $$$x  // $$$ 表示 x 之前的子串，不表示只有三个字符
p @@@y  // @@@ 表示 y 之前的子串，不表示只有三个字符

x = s[i]，y = p[j]，x 匹配 y
s 匹配 p => $$$ 匹配 @@@ => dp[i + 1][j + 1] = dp[i][j]

• 代码为

if (s[i] == p[j] || p[j] == '.') {
  dp[i + 1][j + 1] = dp[i][j];
}

• 第二种情况，如果 p[j] 为 *，这就要看 p[j - 1] 的情况，如果 s[i] 不匹配 p[j - 1]

s $$$x
p @@@y*

x = s[i]，y = p[j - 1]，x 不匹配 y
s 匹配 p => y* 表示空串 => $$$x 匹配 @@@ => dp[i + 1][j + 1] = dp[i + 1][j - 1]

• 如果 s[i] 匹配 p[j - 1]

s $$$x
p @@@x*

s 匹配 p => 分三种情况
1. * 表示 0 个字符 => $$$x 匹配 @@@  => dp[i + 1][j + 1] = dp[i + 1][j - 1]
2. * 表示 1 个字符 => $$$x 匹配 @@@x => dp[i + 1][j + 1] = dp[i + 1][j]
3. * 表示 n 个字符 => $$$  匹配 @@@x*，* 表示 n - 1 个字符 => dp[i + 1][j + 1] = dp[i][j + 1]

情况 3 会不断递归到 * 表示 1 个字符，举一个例子：

s aaa
p a*
* 表示 3 个字符 => aa 匹配 a* => dp[3][2] = dp[2][2]

s aa
p a*
* 表示 2 个字符 => a 匹配 a* => dp[2][2] = dp[1][2]

s a
p a*
* 表示 1 个字符 => dp[1][2] = dp[1][1]

• 第二种情况代码为

if (p[j] == '*') {
  if (s[i] != p[j - 1] && p[j - 1] != '.') {
    dp[i + 1][j + 1] = dp[i + 1][j - 1];
  } else {
    dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
  }
}

• 解法如下

class Solution {
 public:
  bool isMatch(string s, string p) {
    vector<vector<bool>> dp(size(s) + 1, vector<bool>(size(p) + 1));
    dp[0][0] = true;
    for (int i = 2; i < size(dp[0]); i += 2) {
      if (p[i - 1] != '*') {
        break;
      }
      dp[0][i] = true;
    }
    for (int i = 0; i < size(s); ++i) {
      for (int j = 0; j < size(p); ++j) {
        if (s[i] == p[j] || p[j] == '.') {
          dp[i + 1][j + 1] = dp[i][j];
        } else if (p[j] == '*') {
          dp[i + 1][j + 1] = dp[i + 1][j - 1];
          if (s[i] == p[j - 1] || p[j - 1] == '.') {
            dp[i + 1][j + 1] = dp[i + 1][j + 1] || dp[i + 1][j] || dp[i][j + 1];
          }
        }
      }
    }
    return dp[size(s)][size(p)];
  }
};