10.正则表达式匹配，动态规划

linwt · linwt · commit 219c9f17c44e · 2022-04-17T23:22:58.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -4,6 +4,7 @@
 4. 寻找两个有序数组的中位数
 5. 最长回文子串
 8. 字符串转换整数 (atoi)
+10. 正则表达式匹配
 11. 盛最多水的容器
 15. 三数之和
 17. 电话号码的字母组合
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -55,6 +55,7 @@
 
 三、动态规划
 5. 最长回文子串
+10. 正则表达式匹配
 22. 括号生成
 32. 最长有效括号
 42. 接雨水
diff --git a/leetcode_Java/Solution0010.java b/leetcode_Java/Solution0010.java
@@ -0,0 +1,79 @@
+// 10. 正则表达式匹配
+
+
+/*
+1、定义dp数组：dp[i][j] 表示 s 的前 i 个字符是否能被 p 的前 j 个字符匹配
+2、初始化
+  1）s为空，p为空，能匹配
+  2）p为空，s不为空，不能匹配。boolean数组默认值为false，无需处理
+  3）s为空，p不为空，由于*可以匹配0个字符，所以可能匹配
+3、状态转移方程
+  1）s[i]是{字母}，p[j]是{字母，点，星}
+  2）s[i]字母 与 p[j]字母：两者相等则dp[i][j]看前一项即可，所以dp[i][j] = dp[i-1][j-1]。两者不等则不能匹配
+  3）s[i]字母 与 p[j]点：点能配任何一个字母，所以两者必然相等，所以dp[i][j]看前一项即可，所以dp[i][j] = dp[i-1][j-1]
+  4）s[i]字母 与 p[j]星：星代表零个或多个前面的那一个元素
+    ① 若为0个，匹配0次的情况，则代表删掉了p[j-1]和p[j]，所以此时dp[i][j] = dp[i][j-2]
+    ③ 若为多个，匹配1次或多次的情况，如果s[i] == p[j-1] || p[j-1] == '.'，即s的末尾字符与p的末尾前一字符匹配，
+      那么可以忽略s的末尾字符，因为p的末尾可以匹配1个或多个，此时dp[i][j] = dp[i-1][j]
+4、遍历dp数组填表：第一个for循环遍历字符串s，第二个for循环遍历字符串p
+5、返回结果：最后一个状态就是结果
+
+======== 3-2 =========
+s = "abc", p = "abc"
+       ↑          ↑
+       i          j
+======== 3-3 =========
+s = "abc", p = "ab."
+       ↑          ↑
+       i          j
+======== 3-4-1 =======
+s = "a", p = "ab*"
+     ↑          ↑
+     i          j
+======== 3-4-2 =======
+s = "acc", p = "ac*"
+       ↑          ↑
+       i          j
+s = "acc", p = "ac*"
+      ↑           ↑
+      i           j
+s = "acc", p = "ac*"
+     ↑            ↑
+     i            j
+======== 3-4-2 =======
+s = "acc", p = "a.*"
+       ↑          ↑
+       i          j
+ */
+class Solution {
+    public boolean isMatch(String s, String p) {
+        if (s == null || p == null) {
+            return false;
+        }
+        int m = s.length(), n = p.length();
+        boolean[][] dp = new boolean[m + 1][n + 1];
+        dp[0][0] = true;
+        for (int i = 2; i <= n; i += 2) {
+            if (p.charAt(i - 1) == '*') {
+                dp[0][i] = dp[0][i - 2];
+            }
+        }
+        for (int i = 1; i <= m; i++) {
+            for (int j = 1; j <= n; j++) {
+                char sc = s.charAt(i - 1);
+                char pc = p.charAt(j - 1);
+                char pcPre = p.charAt(j - 2);
+                if (sc == pc || pc == '.') {
+                    dp[i][j] = dp[i - 1][j - 1];
+                } else if (pc == '*') {
+                    if (dp[i][j - 2]) {
+                        dp[i][j] = true;
+                    } else if (sc == pcPre || pcPre == '.') {
+                        dp[i][j] = dp[i - 1][j];
+                    }
+                }
+            }
+        }
+        return dp[m][n];
+    }
+}
