10. Regular Expression Matching
in LeetCode with 0 comment

10. Regular Expression Matching

in LeetCode with 0 comment

题目

10. Regular Expression Matching


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).

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

递归法

递归讨论,存在两种情况

  1. p的第二个不是 * ,那就正常处理
  2. p的第二个是 *

那么两种情况下可以继续

while (i < s_len && (i < 0 || p[0] == '.' || p[0] == s[i])) {
    if (isMatch(s.substr(i + 1, s_len - i - 1), p.substr(2, p_len - 2))) return true;
    ++i;
}

其实这块仔细考虑一下,只要出现了 .* 这个组合,肯定是True。

代码为:

class Solution1 {//递归法
public:
    bool isMatch(string s, string p) {

        int s_len = s.length();
        int p_len = p.length();
        if (p_len == 0) return s_len == 0;
        if (p_len == 1 || p[1] != '*') {//p第二个不是*
            if (s_len < 1 || (s[0] != p[0] && p[0] != '.')) return false;
            return isMatch(s.substr(1, s_len - 1), p.substr(1, p_len - 1));
        }
        else {//p第二个是*
            int i = -1;
            while (i < s_len && (i < 0 || p[0] == '.' || p[0] == s[i])) {
                if (isMatch(s.substr(i + 1, s_len - i - 1), p.substr(2, p_len - 2))) return true;
                ++i;
            }
            return false;
        }
    }
};

动态规划

We define the state dp[i][j] to be true if s[0..i) matches p[0..j) and false otherwise.

Then the state equations are:

1、dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2、dp[i][j] = dp[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
dpi 与 dpi 结果相同,将p[j-1] ('*') 直接跳过
3、dp[i][j] = dp[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.
s[i-1] == p[j-2] 这个时候 p[j-1] == '*' ,即相当于匹配了一次.

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                return dp[m][n];
    }
};
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号