LeetCode 解答 #44. Wildcard Matching プログラミング練習

問題：

難易度:　hard
入力:　String s と String p
目的: sがpのパターンと一致するかを判断せよ
出力:　boolean

正規表現的なものを判断する問題です。
＊は任意の文字列を表し、？は任意の文字を表します。
なのでpが'*'であった場合はすべての文字列が該当するので必ずtrueになります。
例の様に、注意するケースは?と＊が乱立しているパターンで、
例えば'a*bc?*'等は要注意です。
正規表現程難しくないです。

注意すべき事:　

• sは小文字の’a-z’を含む

• pは小文字の'a-z'と'*'と'?'を含む

以下回答です。

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

ダイナミックプログラミングを使いました。
二次元のdynamic Arrayを用意します。
まずは先頭が*である場合、任意の文字列を表すのでその前の盤をtrueに置きます。
続いてsとpを照り合わせていきます。
(0,0)はあらかじめtrueに置いており、
s[i] = p[j]　の場合はdp[i-1][j-1]に依存します。
前の文字列もあっていた場合はtrue、
違っている場合はfalseに置きます。

の場合は前の[i-1][j]と[i][j-1]の位置を観察し、決定します。

最後の位置までtrueだった場合一致することになります。

今日は以上。
よいプログラミング生活を！