image.png

方法一：动态规划

这个问题和之前一个题目类似，最先想到的是动态规划。

从后向前分析，看最后一个字母是否匹配

  • 如果最后一个字母不匹配，那么匹配失败，最终结果就是 false
  • 如果最后一个字母匹配，那么继续向前匹配，如果匹配成功再继续向前匹配，知道匹配失败或者全部匹配完毕。

因为题目中有两个字符串，是否匹配也只有一个唯一的答案 true or false ，所以我们可以使用一个二维数组存放是否匹配。就是说 dp[i][j]= true 的意思是字符串 s 中的前 i 个元素和匹配字符串 p 的前 j 个元素是匹配的。

那么怎么判定是否匹配呢？分三种情况

  • 如果为两个字母：直接比较字母是否相等
  • 如果为 ? 那么就认为字符串 s[i] 和 p[j] 匹配成功
  • 如果是 * 也是最复杂的一种情况
    • 匹配 0 个字符 dp[i][j - 1]
    • 匹配多个字符 dp[i - 1][j]

那么最后， dp[i][j] 就是最后的答案。

因为自己代码写的太垃圾了了，就贴一个官方的代码吧

  1. class Solution {
  2. public:
  3.     bool isMatch(string s, string p) {
  4.         int m = s.size();
  5.         int n = p.size();
  6.         vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  7.         dp[0][0] = true;
  8.         for (int i = 1; i <= n; ++i) {
  9.             if (p[i - 1] == '*') {
  10.                 dp[0][i] = true;
  11.             }
  12.             else {
  13.                 break;
  14.             }
  15.         }
  16.         for (int i = 1; i <= m; ++i) {
  17.             for (int j = 1; j <= n; ++j) {
  18.                 if (p[j - 1] == '*') {
  19.                     dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
  20.                 }
  21.                 else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
  22.                     dp[i][j] = dp[i - 1][j - 1];
  23.                 }
  24.             }
  25.         }
  26.         return dp[m][n];
  27.     }
  28. };
  30. 作者：LeetCode-Solution
  31. 链接：https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode-solution/
  32. 来源：力扣（LeetCode）
  33. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。