アルゴリズム--正規表現の一致

タイトル
Given an input string ( s ) and a pattern ( p ), implement regular expression matching with support for  '.'  and  '*' .

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

1.再帰解
考え方:
patternの長いから再帰終了条件を考える.
1.patternの長さが0の場合、sの長さも0の場合trueを返す
2.patternの長さが1の場合、s.charAt(0)=p.charAt(0)またはp.charAt(0)='.'の場合、trueを返します.
3.patternの長さが1より大きい場合、p.charAt(1)が'*'でない場合、比較は2.そうでない場合、状況別に比較する.
(1)s.charAt(0)=p.charAt(0)またはp.charAt(0)='.'すると、sとp.substring(2)またはs.substring(1)とpを比較し続け、一致に成功すればtrueを返す.
    (2)s.charAt(0)!=p.charAt(0)、sとp.substring(2)を比較
コード#コード#

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0){
            return s.length()==0;
        }
        
        if (p.length() == 1 || p.charAt(1) != '*'){
            if (s.length() !=0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){
                return isMatch(s.substring(1),p.substring(1));
            } else {
                return false;
            }
        }
        
        while(s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){
            if (isMatch(s,p.substring(2))){
                return true;
            }
            s = s.substring(1);
        }
        
        return isMatch(s,p.substring(2));
    }
}

2.動的計画
考え方:
dp[i][j]がtrueでs.substring(0,i)がp.substring(0,j)と一致すると仮定する
p.charAt(j)=s.charAt(i)の場合、dp[i][j]=dp[i-1][j-1]
p.charAt(j)='.'時、dp[i][j]=dp[i-1][j-1]
p.charAt(j)='*'の場合
    (1) if s.charAt(i)!=p.charAt(j-1),dp[i][j] = dp[i][j-2]
    (2) if s.charAt(i)==p.charAt(j-1) || p.charAt(i)=='.',dp[i][j]=dp[i-1][j] or dp[i][j]=dp[i][j-1] or dp[i][j]=dp[i][j-2]
コード#コード#

class Solution {
    public boolean isMatch(String s, String p) {
       if (s == null || p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
            }
        }
        
        for (int i = 0 ; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    } else {
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                    }
                }
            }
        }
        
        return dp[s.length()][p.length()];
    }
}