[LeetCode] 10. Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

正则表达式匹配。题意是给一个字符串S和一个字符规律P，请你完成S和P的正则匹配。规则如下，点可以表示/替换任何字符；星号可以代替0个或多个之前的字符。

这个题是一个二维DP题。这个题DP的含义不难想，难的是如何处理好各种case。这里我们需要明确dp[i][j]的含义，是S的前i个字符与P的前J个字符是否match。为了看S的前i个字符与P的前J个字符是否match，比较直观的想法就是去看他们各自之前一个位置的DP情况，即dp[i - 1][j - 1]，但是对于当前位置，会有如下几种情况需要考虑。参考了LC中文网一个大神的总结。

1. 如果 p[j] == s[i]，那么dp[i][j] = dp[i-1][j-1]

2. 如果p[j] != s[i]，即当前遍历到的字符不匹配

　　2.1. p[j] == "." : dp[i][j] = dp[i-1][j-1]，因为点可以替换任何字符，只要去看之前那一位的字符是否匹配即可。这个case等同于第一个case。

　　2.2. p[j] ==" * "，这个又需要细分成以下两种情况。因为星号可以代替0个或多个在他之前的那个字符，所以需要看p[j - 1]和s[i]的情况

　　　　2.2.1. p[j-1] != s[i] : dp[i][j] = dp[i][j-2]

　　　　这里设想的是星号去掉了他自己和他自己之前的那个字符，比如这个例子，s = ab, p = abc*

　　　　2.2.2. p[j-1] == s[i] or p[j-1] == "."。星号前面那个字符，能匹配 s[i]，或者星号前面那个字符是万能的点。因为星号+点就等同于两个点，只要看再前面的部分是否匹配即可。比如s == aa, p = a*

时间O(mn)

空间O(mn)

Java实现

 1 class Solution {
 2     public boolean isMatch(String s, String p) {
 3         // corner case
 4         int m = s.length();
 5         int n = p.length();
 6         boolean[][] dp = new boolean[m + 1][n + 1];
 7         dp[0][0] = true;
 8 
 9         // 星号匹配前面0个字符
10         for (int i = 2; i <= n; i++) {
11             if (p.charAt(i - 1) == '*') {
12                 dp[0][i] = dp[0][i - 2];
13             }
14         }
15 
16         for (int i = 1; i <= m; i++) {
17             for (int j = 1; j <= n; j++) {
18                 char sc = s.charAt(i - 1);
19                 char pc = p.charAt(j - 1);
20                 if (sc == pc || pc == '.') {
21                     dp[i][j] = dp[i - 1][j - 1];
22                 } else if (pc == '*') {
23                     // * matches zero preceding letters
24                     if (dp[i][j - 2]) {
25                         dp[i][j] = true;
26                     }
27                     // * matches one preceding letter
28                     // aa - a*
29                     else if (sc == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
30                         dp[i][j] = dp[i - 1][j];
31                     }
32                 }
33             }
34         }
35         return dp[m][n];
36     }
37 }

LeetCode 题目总结