LeetCode 10 Regular Expression Matching

Posted on | In | 阅读

动态规划

Implement regular expression matching with support for '.' and '*'.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> '.' Matches any single character.
> '*' Matches zero or more of the preceding element.
>
> The matching should cover the entire input string (not partial).
>
> The function prototype should be:
> bool isMatch(const char *s, const char *p)
>
> Some examples:
> isMatch("aa","a") → false
> isMatch("aa","aa") → true
> isMatch("aaa","aa") → false
> isMatch("aa", "a*") → true
> isMatch("aa", ".*") → true
> isMatch("ab", ".*") → true
> isMatch("aab", "c*a*b") → true
>
>

动态规划问题dp[i][j]代表s[i]之前（不算i）与p[j]之前的字符串是否能够匹配

初始化：

  • dp[0][0] = true
  • dp[i][0] = false when i >= 1
  • dp[0][j] = j > 1 && p[j-1] == '*' && dp[0][j-2] 即只有都可以用*来代替掉的情况才能是true

两种更新情况：

  • p[j-1] == '*'

    • dp[i][j] = dp[i][j - 2] // i与j-2可以匹配的情况下，这个*代表0次
    • dp[i][j] = (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j] // 在i-1 与 j可以匹配的情况下 这个*代表一次或多次

  • p[j-1] != '*'

    dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1] //在i-1与j-1可以匹配的情况下 i 与 j 能够匹配

由于这题Python直接就有函数可以解决，所以改用C++来练习

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool isMatch(string s, string p) {
        int lens = s.length();
        int lenp = p.length();
        
        bool **dp = new bool *[lens+1];
        for(int i = 0; i <= lens; i++)
            dp[i] = new bool [lenp+1];
        bool res = false;
        dp[0][0] = true;
        for(int i = 1; i <= lens; i++)
        {
            dp[i][0] = false;
        }
        for(int j = 1; j <= lenp; j++)
        {
            if(j > 1 && p[j-1] == '*' && dp[0][j-2])
                dp[0][j] = true;
            else
                dp[0][j] = false;
        }
        
        for(int i = 1; i <= lens; i++)
        {
            for(int j = 1; j <= lenp; j++)
            {
                if(p[j-1] == '*')
                {
                    dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
                }
                else
                {
                    dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
                }
            }
        }
        res = dp[lens][lenp];
        for(int i = 0; i <= lens; i++)
            delete [] dp[i];
        delete [] dp;
        return res;
    }
};