Leetcode 10. Regular Expression Matching(递归，dp)

10. Regular Expression Matching

Hard

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 = "a*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:

s = "ab"

p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:

s = "aab"

p = "c*a*b"

Output: true

Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:

s = "mississippi"

p = "mis*is*p*."

Output: false

题解：这个题如果用暴力的想法很难想清楚，因为对于.*的处理很难，但是如果我们理解.*可匹配也可不匹配这样一个性质就很容易联想递归或者DP的思路了：

这道题分的情况的要复杂一些，先给出递归的解法：

- 若p为空，且s也为空，返回true，反之返回false

- 若p的长度为1，且s长度也为1，且相同或是p为'.'则返回true，反之返回false

- 若p的第二个字符不为*，且此时s为空则返回false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配

- 若p的第二个字符为*，s不为空且字符匹配，调用递归函数匹配s和去掉前两个字符的p，若匹配返回true，否则s去掉首字母

- 返回调用递归函数匹配s和去掉前两个字符的p的结果

由于我对递归结束的判断实在是太恶心了。。。。于是时间和空间都很慢，不过因为是最好理解的思路，所以还是把代码扔上来：

 class Solution {

 public:

     int in(char ch){

         if(ch=='.') return ;

         else if(ch=='*') return ;

         else return ;

     }

     bool isMatch(string s, string p) {

         int lens = s.length();int lenp = p.length();

         if(lens== && lenp==) { return ;}

         if(lens== && lenp== && s[]==p[]) {return ;}

         if(lens== && lenp==) return ;

         if(lens!= && lenp==) { return ;}

         if(lens==){

             if((in(p[])==&&in(p[])!=)||(in(p[])== &&in(p[])!=)) return ;

             if(in(p[])==) return isMatch(s,p.substr(,lenp));

         }

         if(in(p[])==&&in(p[])!=){

             if(lens==||p[]!=s[]) { return ;}

             else return isMatch(s.substr(,lens),p.substr(,lenp));

         }

         if(in(p[])==&&in(p[])!=){

             if(lens==) { return ;}

             else return isMatch(s.substr(,lens),p.substr(,lenp));

         }

         if(in(p[])==&&in(p[])==){

             if(p[]!=s[]) return isMatch(s,p.substr(,lenp));

             else return max(isMatch(s.substr(,lens),p),isMatch(s,p.substr(,lenp)));

         }

         if(in(p[])==&&in(p[])==)

             return max(isMatch(s.substr(,lens),p),isMatch(s,p.substr(,lenp)));

         cout<<<<endl; return ;

     }

 };

后来在网上看到了大佬原来可以这么写

 class Solution {

 public:

     bool isMatch(string s, string p) {

         if (p.empty()) return s.empty();

         if (p.size() >  && p[] == '*') {

             return isMatch(s, p.substr()) || (!s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p));

         } else {

             return !s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p.substr());

         }

     }

 };

我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况(下面部分摘自：https://leetcode.com/problems/regular-expression-matching/discuss/5684/9-lines-16ms-c-dp-solutions-with-explanations)：

1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3.
P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] ==
'.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

 class Solution {

 public:

     bool isMatch(string s, string p) {

         int m = s.size(), n = p.size();

         vector<vector<bool>> dp(m + , vector<bool>(n + , false));

         dp[][] = true;

         for (int i = ; i <= m; ++i) {

             for (int j = ; j <= n; ++j) {

                 if (j >  && p[j - ] == '*') {

                     dp[i][j] = dp[i][j - ] || (i >  && (s[i - ] == p[j - ] || p[j - ] == '.') && dp[i - ][j]);

                 } else {

                     dp[i][j] = i >  && dp[i - ][j - ] && (s[i - ] == p[j - ] || p[j - ] == '.');

                 }

             }

         }

         return dp[m][n];

     }

 };

巴特西

Leetcode 10. Regular Expression Matching(递归，dp)

最新文章

热门文章