题目

regular-expression-matching

算法

* 递归方法

http://www.jianshu.com/p/85f3e5a9fcda

o(n!)

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

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

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

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

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

* DP

* O(nm)

http://www.ithao123.cn/content-7140020.html http://mingyi.js.org/2017/02/20/LeeCode10-Regular-Expression-Matching/

* dp[i][j] 表示s[0, i-1] 和 p[0, j-1]是否匹配
* 初始解:
    * dp[0][0] = true; // 两个空字符串
    * dp[0][1] 和 dp[1][0] 均是false
* 状态转义方程：
    * 如果p[j - 1]不是*也不是.则判断 s[i - 1] == p[j - 1] && dp[i - 1][j - 1]
    * 如果p[j - 1]是. 则dp[i][j] = dp[i - 1][j - 1]
    * 如果p[j - 1]是* 则分三种情况
        * 1. 匹配0个  dp[i][j] = dp[i][j - 2]
        * 2. 匹配1个  dp[i][j] = dp[i][j - 1]
        * 3. 匹配多个 dp[i][j] = dp[i - 1][j] && s[i - 1] == p[j - 2] || p[j - 2] == '.'

代码

递归方法

class solution{
public:
    bool isMatch(string s,string p){
        if(p.empty()) return s.empty();
        if(p.size()==1)
            return (s.size()==1 && (s[0]==p[0]|| p[0]=='.'));
        if(p[1]!='*'){
            if(s.empty())  return false;
            return (s[0]==p[0] || p[0]=='.')  && isMatch(s.substr(1),p.substr(1));
        }
        while(!s.empty() && (s[0]==p[0] || p[0]=='.')){
            if(isMatch(s,p.substr(2))) return true;
            s=s.substr(1);
        }

        return isMatch(s,p.substr(2));
    }
};

迭代方法的简化

http://www.cnblogs.com/grandyang/p/4461713.html

class solution{
public:
    bool isMatch(string s,string p){
        if(p.empty()) return s.empty();
        if(p.size()==1)
            return (s.size()==1 && (s[0]==p[0]|| p[0]=='.'));
        if(p[1]!='*'){
            if(s.empty())  return false;
            return (s[0]==p[0] || p[0]=='.')  && isMatch(s.substr(1),p.substr(1));
        }
        while(!s.empty() && (s[0]==p[0] || p[0]=='.')){
            if(isMatch(s,p.substr(2))) return true;
            s=s.substr(1);
        }

        return isMatch(s,p.substr(2));
    }
};

dp

class Solution {
public:
    bool isMatch(string s, string p) {
        int lens = s.length(), lenp = p.length();
        vector<vector<bool>> dp(lens + 1, vector<bool>(lenp + 1, false));
        dp[0][0] = true;

        for (int i = 0; i < lens + 1; i++) {
            for (int j = 1; j < lenp + 1; j++) {
                if (p[j - 1] != '.' && p[j - 1] != '*') {
                    if (i > 0 && s[i - 1] == p[j - 1] && dp[i - 1][j - 1]) {
                        dp[i][j] = true;
                    }
                } else if (p[j - 1] == '.') {
                    if (i > 0 && dp[i - 1][j - 1]) {
                        dp[i][j] = true;
                    }
                } else if (j > 1) {
                    if (dp[i][j - 2] || dp[i][j - 1]) {
                        dp[i][j] = true;
                    } else if (i > 0 && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) {
                        dp[i][j] = true;
                    }
                }
            }
        }

        return dp[lens][lenp];
    }
};