leetcode第1ブラシ_Regular Expression Matching

この問題はついていますか.*の問題と似ていますが、簡単にしてください.なぜなら、*番号は前と同じ文字にしか一致しないからです.注意しなければならないのは、aabがc*a*bでマッチングできることから、*番号は彼の前の文字の出現回数を0にすることができることです.
昨日実験室の同級生はちょうどこの問題をしていて、再帰でやりたいと言っていましたが、私は考えていないと思って、再帰でタイムアウトしたに違いありません.彼女はどうして、私は人に再帰の分岐が多すぎると言ったが、どうして当初自分がどのように書いたのか思い出せないのか、帰ってみると、意外にも再帰で作ったので、顔を殴ったのか.この問題はどうして再帰でいいのですか.主に*番のマッチングルールのため、任意の文字にマッチングできるよりも、以前の文字にしかマッチングできないのが厳しく、多くの分岐が切られていると思います.
はい、全体の考え方が再帰であることを確定しました.具体的にはどうしますか.再帰の分岐はどうやって行ったのか考えてみましょう.同じように、2つの記号のうち、'.'私たちにとって脅威ではありません.多くの状況があるのは、*のためです.私たちは*によって区別することができます.それは現在の位置によって*で区別されているのではないでしょうか.No no noは、*が前の文字にマッチしているので、その前の文字の位置で*の問題を考えることができ、現在の位置の後の文字が*かどうかによって区別するのは良い選択です.
現在の位置がiであると仮定し、i+1の位置が*でないと仮定すると、iの位置は完全に一致しなければならない.ここでの完全な一致は、文字が同じか、p[i]='.'の2つの場合に分けられる.注意'.'実際の文字と一致しなければならず、'0'に一致しません.i+1の位置が*であればブランチが来て、現在の位置が一致しない場合は、この*でp[i]の出現回数が0になる、すなわちp+2の位置をマッチングし続けるしかない.現在の位置が一致している場合は、p[i]で複数回(このときのsの更新ポインタ)をマッチングしてもよいし、この文字をスキップしてもよい(分岐はp+2をマッチングすることによって).
コードを書くと簡単に紹介されます.

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(s==NULL && p == NULL)    return false;
        if(*p=='\0') return *s=='\0';
        if(*(p+1) != '*'){
            return (*s==*p||(*p=='.'&&*s != '\0'))&&isMatch(s+1, p+1);
        }
        while(*p==*s || (*p=='.'&&*s!='\0')){
            if(isMatch(s, p+2)) return true;
            ++s;
        }
        return isMatch(s, p+2);
    }
};