BM76 正则表达式匹配
具体实现:
1.确定dp数组以及下标的含义
dp[i][j]代表s中以i结尾的子串和p中j为结尾的子串是否匹配
2.状态转移
(1)p[j]为普通字符:匹配的条件是前面的字符匹配,同时 s
中的第 i
个字符和 p
中的第 j
位相同。
即 dp[i][j] = dp[i - 1][ j - 1] && s[i] == p[j]
。
(2)p[j]为'.':匹配的条件是前面的字符匹配,s
中的第 i
个字符可以是任意字符。
即 dp[i][j] = dp[i - 1][ j - 1] && p[j] == '.'
。
(3)p[j]为‘*’:假设p[j - 1]的字符为a,然后根据a*十几匹配s中a的个数是0个、1个、2个。。。。
3.1 当匹配为0个:dp[i][j] = dp[i][j - 2]
3.2 当匹配为1个:dp[i][j] = dp[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')
3.3 当匹配为2个:dp[i][j] = dp[i - 2][j - 2] && ((s[i] == p[j - 1] && s[i - 1] == p[j - 1]) || p[j - 1] == '.')
表达式展开:
dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] && (s[i] 匹配 p[j - 1]) || dp[i - 2][j - 2] && ((s[i], s[i - 1] 匹配 p[j - 1]) || ........
i = i - 1代入
dp[i - 1][j] = dp[i - 1][j - 2] || dp[i - 2][j - 2] && (s[i - 1] 匹配 p[j - 1]) || dp[i - 3][j - 2] && ((s[i - 1], s[i - 2] 匹配 p[j - 1]) || ........
dp[i - 1][j]从第二项开始每个item都比dp[i][j]相差了s[i]匹配p[j-1]
dp[i][j] = dp[i][j - 2](dp[i][j] 的第一项) || (dp[i - 1][j] && s[i]匹配p[j-1])
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i]==p[j-1] || p[j-1] == '.'))
import java.util.*; public class Solution { public boolean match (String ss, String pp) { // 技巧:往原字符头部插入空格,这样得到 char 数组是从 1 开始,而且可以使得 f[0][0] = true,可以将 true 这个结果滚动下去 int n = ss.length(), m = pp.length(); ss = " " + ss; pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); // f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配 boolean[][] f = new boolean[n + 1][m + 1]; f[0][0] = true; for (int i = 0; i <= n; i++) { for (int j = 1; j <= m; j++) { // 如果下一个字符是 '*',则代表当前字符不能被单独使用,跳过 if (j + 1 <= m && p[j + 1] == '*') continue; // 对应了 p[j] 为普通字符和 '.' 的两种情况 if (i - 1 >= 0 && p[j] != '*') { f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.'); } // 对应了 p[j] 为 '*' 的情况 else if (p[j] == '*') { f[i][j] = (j - 2 >= 0 && f[i][j - 2]) || (i - 1 >= 0 && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')); } } } return f[n][m]; } }
- 时间复杂度:n 表示 s 的长度,m 表示 p 的长度,总共 n * mn∗m 个状态。复杂度为 O(n * m)O(n∗m)
- 空间复杂度:使用了二维数组记录结果。复杂度为 O(n * m)O(n∗m)