剣指offer——正規表現マッチング(c++)

タイトルの説明'.'および'*'を含む正規表現を一致させるための関数を実装してください.パターン内の文字'.'は任意の文字を表し、'*'はその前の文字が任意の回数(0回を含む)現れることを表す.本題では、マッチングとは、文字列のすべての文字がモード全体に一致することを意味します.例えば、文字列「aaa」は、パターン「a.a」および「ab*ac*a」と一致するが、「aa.a」および「ab*a」と一致しない.サンプル

  ：
s="aa"
p="a*"
  :true

考えが再帰する.
モードの次の文字が'*'の場合、現在の文字が一致する場合、文字列が1ビット後方に移動するか、モードが2ビット後方に移動するかの2つのケースに分けられます.逆に、現在の文字が一致しない場合、モードは2ビット後方に移動します.モードの次の文字が'*'でない場合、現在の文字が一致している場合、またはモードが'.'である場合、次の文字を一致させ続け、そうでない場合falseを返します.

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty())
            return s.empty();
        return match(s, p, 0, 0);
    }
    bool match(string s, string p, int i, int j){
    	//        ，     ，   true
        if(i == s.size() && j == p.size())
            return true;
        //p     ，  s       ，     
        if(i != s.size() && j == p.size())
            return false;
        if(p[j+1] == '*'){
            if(s[i] == p[j] || (i < s.size() &&  p[j] == '.'))
                return match(s, p, i+1, j) || match(s, p, i, j+2);
            else
                return match(s, p, i, j+2);
        }
        else{
            if(s[i] == p[j] || (i < s.size() && p[j] == '.'))
                return match(s, p, i+1, j+1);
            else
                return false;
        }
    }
};

構想動的計画
2 D DP配列を定義し、dp[i][j]はs[0,i)とp[0,j)がmatchであるか否かを表し、以下の3つのケース(以下、Leetcodeより抜粋)がある.

P[i][j] = P[i - 1][j - 1] , if p[j - 1] != '*'&& (s[i - 1] == p[j - 1] || p[j - 1] == '.') ;

P[i][j] = P[i][j - 2] , if p[j - 1] == '*' and the pattern repeats for 0 times;

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 + 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 (j > 1 && 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];
    }
};