LeetCode 10. Regular Expression Matching 正则表达式匹配

Description

link

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

Solution

题意：给出字符串str和模式p(pattern),模式p中'.'可匹配任意单个字符，'*'匹配前一个单字符的幂即0个或多个重复的该字符。str中所有字符被完全匹配则输出true，否则false。

错误思路：我刚开始的思路有些偏差，没有向递归和动态规划方向考虑。我遍历模式串p，判断是否是带'\*'的字符，并记录当前模式字符nowP，如果带'\*'则从str串中遍历nowP直到不匹配跳出，否则匹配当前字符，进入下一个模式字符循环，最后看是否str串中匹配完全并返回值。虽然本方法也能通过部分样例，但对于以下例子可以正确匹配的情况却给出了false的值。此方法不能识别像'a*'和'a'之间的情况。错误代码附文末，可请大家帮忙debug。

“aaa” “abac*a”

1. 递归法 Recursion

上述错误的思路根源在于没有将字符串看成整体进行匹配，只是简单的比较了局部的子串。采用递归算法，可将问题分解为一个个子问题，从前往后开始递归判断串str和模式p是否匹配，可分为两种情况：

如果当前模式p首字符带'\*'，则可忽视这个'p*'（对应0次幂）直接用下一个模式匹配当前子串，或者对比当前字符后继续用这个模式（对应多次幂）匹配下一个子串；
如果当前模式p首字符不带'\*'，则直接匹配当前字符是否相同或者模式为'.'字符，专向下一个模式去匹配下一个子串的子问题。

代码如下 (Java)：

class Solution {
    public boolean isMatch(String s, String p) {
        
        if(p.isEmpty()) return s.isEmpty();
        
        boolean first_match = (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        
        if(p.length() >= 2 && p.charAt(1) == '*')
        {
            //substring(index)是去掉原串的前index个之后的子串（或直接去原串中下标index~末尾的子串）
            return isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p));
        }
        else
        {
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
        
    }
}

Complexity Analysis: · Time complexity : O((T+P)2^{T+P/2}). · Space complexity : O(T^2 + P^2).

2. 动态规划 Dynamic Programming

根据递归算法可知，本问题存在最优子结构，可以用动态规划的方法存储中间结构。用dp(i,j)表示子串str[i:]和模式p[j:]是否匹配。初始化dp[T][P]=true表示空子串和空模式匹配成功为true，从后往前开始更新，最后输出dp[0][0]即为最终结果。循环需从子串str[T:]开始更新，原因是遇到'p*'这种模式串时可为true的结果。更新原理和递归法一致。

代码如下(Java)：

class Solution {
    public boolean isMatch(String s, String p) {
        
        boolean dp[][] = new boolean[s.length()+1][p.length()+1];
        dp[s.length()][p.length()] = true;
        
        for(int i=s.length(); i>=0; i--)
        {
            for(int j=p.length()-1; j>=0; j--)
            {
                boolean first_match = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                
                if(j+1 < p.length() && p.charAt(j+1) == '*')
                {
                    dp[i][j] = dp[i][j+2] || (first_match && dp[i+1][j]);
                }
                else
                {
                    dp[i][j] = (first_match && dp[i+1][j+1]);
                }
                
            }
        }
        
        return dp[0][0];
    }
}

Complexity Analysis · Time Complexity: Let T, PT,P be the lengths of the text and the pattern respectively. The >work for every call to dp(i, j) for i=0, … ,Ti=0,…,T; j=0, … ,Pj=0,…,P is done once, >and it is O(1) work. Hence, the time complexity is O(TP). · Space complexity : The only memory we use is the O(TP) boolean entries in our cache. >Hence, the space complexity is O(TP).

附：错误思路代码

class Solution {
    public boolean isMatch(String s, String p) {
        
        int j=0, i=0;

        for(i=0; i<p.length() && j<s.length(); )
        {
            char now = p.charAt(i);
            boolean mul = false;
            int cnt = 0;  //表示 * 后出现前一个元素的个数
            if(i+1 < p.length() && p.charAt(i+1) == '*')
            {
                mul = true;
                i += 2;
                for(; i<p.length(); i++)
                {
                    if(p.charAt(i) == now)
                    {
                        cnt++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            else
            {
                i++;
            }
            
            if(mul)
            {
                int flag = 0;
                if(s.charAt(j) == now || now == '.')
                {
                    for(; j<s.length(); j++)
                    {
                        if(s.charAt(j) == now || now == '.')
                        {
                            flag++;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                
                if(flag < cnt) return false;
            }
            else
            {
                if(s.charAt(j) == now || now == '.')
                {
                    j++;
                }
                else
                {
                    return false;
                }
            }
        }
        
        for(int k=i; k<p.length(); )
        {
            if(k+1 < p.length() && p.charAt(k+1) == '*')
            {
                k += 2;
            }
            else if(p.charAt(k) == '*')
            {
                k++;
            }
            else
            {
                return false;
            }
        }
        
        return j == s.length();
    }
}

LeetCode 10. Regular Expression Matching

2018年02月02日，正则表达式匹配