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号