LeetCode[ダイナミックプランニング]-〹10 Reglar Expression Match ing

ソースリンク：癜10 Reglar Expression Match ing
 
要求:
正規表現のマッチングを行います。''''と'*'をサポートします。
 
''は任意の単文字にマッチします。
'*'は任意の0つ以上の前の要素にマッチします。
 
マッチは、入力文字列全体をカバーします。サブストリングだけではありません。
 
関数のプロトタイプ:
bootlean isMatch(String/*string to check*/s，String/*patterns*/p)
 
例:
isMatch(「a a」「a」)→false
isMatch(「aa」、「aa」)→true
isMatch(「aaa」「aa」)→false 
isMatch(「aa」、「.*」)→true
isMatch(「ab」、「.*」)→true
isMatch(「a b」、「c*a*b」)→true
 
難易度：難しい
 
分析:
元の問題で示した6つの例だけを考えると、貪欲なアルゴリズムを採用し、patterns文字列の末尾から前へスキャンし、patternsの各文字については、検査待ち文字列の中から一番上の子列にマッチするように掃除し、スキャンが終わったら検査待ち文字列の頭に到達するかどうかを判断すればいいです。貪欲アルゴリズムを用いて実現された関数これを見て。しかし、この関数はisMatch（aaaa）、ab＊a＊c＊a）などに対応すると問題が発生し、a＊をスキャンすると検査待ち文字列の頭に到達し、エラー結果が発生するため、貪欲アルゴリズムは適用されない。
 
依然として検査対象文字列の末尾から前へスキャンし、0≦j＜s.length（）を設定し、サブ連結s[J.s.length（）-1]について正則表現pでマッチ（match[j]）を見つけることができる条件をs[j＋1...s.length（）-1）とし、s[j]もparntteでマッチを見つけることができる。s[j]もpatternでマッチを見つけることができるとどう判断しますか？二つの場合に分けて検討したいです。iをpattern索引として、第一の場合：p[i]が「*」でない場合、単文字判定を行い、p[i]==''''またはp[i]==s[j]の時にmatch[j]が成立します。第二の場合：p[i]は「*」であり、match[j]が成立する条件はp[i-1]='、'またはp[i-1]=p[j]である。また、この場合、下若match[j]はすでにtrueとして置かれています。p[i-1]='.'||p==p[j]が成立しなくても、その値を保持しています。
 
ソリューション:
Java-340 ms
    

// Dynamic Programming Solution
    public boolean isMatch(String /* string to check */ s, String /* patterns */ p) {
        boolean[] match = new boolean[s.length()+1];
        for(int i=0; i<match.length; i++){
            match[i] = false;
        }
        match[s.length()] = true;
        for(int i=p.length()-1; i>=0; i--){
            if(p.charAt(i)=='*'){
                for(int j=s.length()-1; j>=0; j--){
                    match[j] = match[j]||match[j+1]&&(p.charAt(i-1)=='.'||p.charAt(i-1)==s.charAt(j));
                }
                i--;
            }else {
                for(int j=0; j<s.length(); j++){
                    match[j] = match[j+1]&&(p.charAt(i)=='.'||p.charAt(i)==s.charAt(j));
                }
                match[s.length()] = false;
            }
        }
        return match[0];
    }

  簡単なテストプログラム