『剣指offer』19--正規表現マッチング[C+]

タイトルの説明
'.'を含む関数をマッチングするために実装してください.と'*'の正規表現です.モードの文字'.'任意の文字を表し、'*'はその前の文字が任意の回数(0回を含む)現れることを示します.本題では、マッチングとは、文字列のすべての文字がモード全体に一致することを意味します.例えば、文字列「aaa」は、パターン「a.a」および「ab*ac*a」と一致するが、「aa.a」および「ab*a」と一致しない.
問題を解く構想.
動的計画どうてきけいかく:上から下への変化じょうから下へのへんか

class Solution {
public:
    bool isMatch_i(char* s, char* p, int start_i, int start_p) {
        int si = start_i, pi = start_p;
        while(pi

ダイナミックプランニングダイナミックプランニング:下から上への変更

class Solution {
public:
    bool match(char* str, char* pattern) {
        return isMatch_i(str, pattern);
    }
    bool isMatch_i(char* s, char* p) {
        int snum = strlen(s);
        int pnum = strlen(p);
        vector > dp(snum + 1, vector(pnum + 1, false));
        dp[0][0] = true;
        for (int i = 2; i < pnum + 1; ++ i) {
            if (p[i-1] == '*') {
                dp[0][i] = dp[0][i-2];
            }
        }
        for (int i = 1; i < snum + 1; ++ i) {
            for (int j = 1; j < pnum + 1; ++ j) {
                if (p[j-1] == '.')  dp[i][j] = dp[i-1][j-1];
                else if (p[j-1] == '*') {
                    dp[i][j] = ( dp[i][j-2] || // p[j-2] p[j-1] match zero
                                 dp[i][j-1] || // p[j-2] p[j-1] match one remove *
                               ((p[j-2] == '.' || p[j-2] == s[i-1]) && dp[i-1][j]) );// p[j-2] p[j-1] match mutil
                } 
                else {dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1];}
            }
        }
        return dp[snum][pnum];
    }
};

以上がLeetCodeの答えで、より厳密にするために、
まず、特別な状況を考慮します.
1>両方の文字列が空で、trueを返します.
2>最初の文字列が空でなく、2番目の文字列が空である場合、falseを返します(これにより、一致に成功しませんが、1番目の文字列が空でなければ、2番目の文字列が空でない場合、一致に成功する可能性があります.例えば、2番目の文字列は「a*a*a*a*a*a*a*」です.「*」の前の要素が0回現れるため、一致に成功する可能性があります).
その後、最初の文字のマッチングが開始されます.ここでは、マッチングに成功したか、マッチングに失敗したかの2つの可能性があります.
しかし、patternの次の文字が「*」である可能性があることを考慮すると、patternの次の文字が「*」であるか、「*」でないかの2つの状況に分けて議論します.
1>pattern次の文字は「*」:この場合は比較的簡単で、現在の文字に直接一致します.マッチングに成功した場合は、次のマッチングを続行します.マッチングに失敗した場合はfalseに直接戻ります.ここでの「マッチング成功」には、2文字が同じ場合に加えて、patternの現在の文字が「.」である場合があります.同時にstrの現在の文字は'0'ではありません.
2>patternの次の文字が「*」の場合、「*」は0つ以上を表すことができるため、少し複雑です.ここでは、これらの状況を考慮します.
a>「*」が0文字に一致するとstrの現在の文字は変わらず、patternの現在の文字は2桁後ろに移動し、この「*」記号をスキップする.
b>「*」が1つ以上一致するとstr現在文字は次の文字にシフトし、pattern現在文字は変わらない.(ここで1つ以上をマッチングすることは、1つをマッチングするとstrが次の文字に移動するためpattern文字が変わらず上の場合aに戻るため、1つ以上をマッチングするとstrの次の文字からマッチングを開始することに相当する)

class Solution {
public:
    bool match(char* str, char* pattern) {
        if(!str || !pattern) return false;
        return matchCore(str, pattern);
    }
    bool matchCore(char* str, char* pattern) {
        if(*pattern == '\0') {
            if(*str == '\0') return true;
            else return false;
        }
        if(*(pattern+1) == '*') {
            if(*str == *pattern || (*str != '\0' && *pattern == '.')) 
                return matchCore(str+1, pattern) || matchCore(str, pattern+2);
            else return matchCore(str, pattern+2);
        }
        if(*str == *pattern || (*str != '\0' && *pattern == '.'))  return matchCore(str+1, pattern+1);
        return false;
    }
};