C++刷LeetCode（剑指 Offer 19. 正则表达式匹配）【动态规划】

糖逗

题目描述:

1. 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入:
   
6. s = "aa"
   
7. p = "a"
   
8. 输出: false
   
9. 解释: "a" 无法匹配 "aa" 整个字符串。
   
10. 示例 2:
    
11. 
    
12. 输入:
    
13. s = "aa"
    
14. p = "a*"
    
15. 输出: true
    
16. 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
    
17. 示例 3:
    
18. 
    
19. 输入:
    
20. s = "ab"
    
21. p = ".*"
    
22. 输出: true
    
23. 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
    
24. 示例 4:
    
25. 
    
26. 输入:
    
27. s = "aab"
    
28. p = "c*a*b"
    
29. 输出: true
    
30. 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
    
31. 示例 5:
    
32. 
    
33. 输入:
    
34. s = "mississippi"
    
35. p = "mis*is*p*."
    
36. 输出: false
    
37. s 可能为空，且只包含从 a-z 的小写字母。
    
38. p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
    
39. 
    
40. 来源：力扣（LeetCode）
    
41. 链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
    
42. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool isMatch(string s, string p) {
   
4.         int len1 = s.size(), len2 = p.size();
   
5.         if(len2 ==0){
   
6.             if(len1 == 0)return true;
   
7.             return false;
   
8.         }
   
9.         if(p[0] == '*')return false;
   
10. 
    
11.         vector<vector<bool> > dp(len1 + 1, vector<bool>(len2 + 1, false));
    
12.         s = " " + s;
    
13.         p = " " + p;
    
14.         dp[0][0] = true;
    
15.         for(int j = 2; j <= len2; j++){
    
16.             if(p[j] == '*')dp[0][j] = dp[0][j-2];
    
17.             else dp[0][j] = false;
    
18.         }
    
19. 
    
20.         for(int i = 1; i <= len1; i++){
    
21.             for(int j = 1; j <= len2; j++){
    
22.                 if(p[j] != '*')dp[i][j] = dp[i-1][j-1] && (s[i] == p[j] || p[j] == '.');
    
23.                 else dp[i][j] = dp[i][j - 2] || dp[i - 1][j] &&(s[i] == p[j-1] || p[j - 1] == '.');
    
24.             }
    
25.         }
    
26.         return dp[len1][len2];
    
27. 
    
28.     }
    
29. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ie-by-acw_wangdh15/
注意事项：这里二层循环j从1而不是从2开始是因为之前已经判断了p[0]不能等于‘*’，因此虽然j从1开始，但是循环到else是从2开始的。

糖逗

相似题目（44. 通配符匹配）：

1. 
   
2. 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
   
3. 
   
4. '?' 可以匹配任何单个字符。
   
5. '*' 可以匹配任意字符串（包括空字符串）。
   
6. 两个字符串完全匹配才算匹配成功。
   
7. 
   
8. 说明:
   
9. 
   
10. s 可能为空，且只包含从 a-z 的小写字母。
    
11. p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
    
12. 示例 1:
    
13. 
    
14. 输入:
    
15. s = "aa"
    
16. p = "a"
    
17. 输出: false
    
18. 解释: "a" 无法匹配 "aa" 整个字符串。
    
19. 示例 2:
    
20. 
    
21. 输入:
    
22. s = "aa"
    
23. p = "*"
    
24. 输出: true
    
25. 解释: '*' 可以匹配任意字符串。
    
26. 示例 3:
    
27. 
    
28. 输入:
    
29. s = "cb"
    
30. p = "?a"
    
31. 输出: false
    
32. 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
    
33. 示例 4:
    
34. 
    
35. 输入:
    
36. s = "adceb"
    
37. p = "*a*b"
    
38. 输出: true
    
39. 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
    
40. 示例 5:
    
41. 
    
42. 输入:
    
43. s = "acdcb"
    
44. p = "a*c?b"
    
45. 输出: false

复制代码

1. lass Solution {
   
2. public:
   
3.     bool isMatch(string s, string p) {
   
4.         int len1 = s.size(), len2 = p.size();
   
5.         vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));
   
6.         s = " " + s;
   
7.         p = " " + p;
   
8.         dp[0][0] = true;
   
9.         for (int j = 1; j <= len2; j++) {
   
10.             if (p[j] == '*') dp[0][j] = dp[0][j-1];
    
11.         }
    
12.         for (int j = 1; j <= len2; j++) {//注意这里的顺序
    
13.             for (int i = 1; i <= len1; i++) {
    
14.                 if (p[j] != '*') dp[i][j] = dp[i-1][j-1] && (s[i] == p[j] || p[j] == '?');
    
15.                 else dp[i][j] = dp[i-1][j] || dp[i][j-1];
    
16.             }
    
17.         }
    
18.         return dp[len1][len2];
    
19.     }
    
20. };

复制代码

糖逗

这道题要之后再好好想想，关于循环的顺序。