LeetCode #10. Regular Expression Matching プログラミング練習
問題：
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.
The matching should cover the entire input string (not partial).Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
難易度: hard
入力: String
目的: 入力された文字列が入力されたパターンと一致するか判断せよ
出力: boolean
難易度hard
正規表現に関する問題です。
私はよくPythonでreライブラリを使って正規表現を使うのですが、
今回はライブラリ無しでマッチング判断をする問題ですね。
当然パターンも制限されており、a-z . *のみが入力になります。
回答方法は色々あると思います。
greedy, deep first search, dynamic programming
で答えられると思いますが、
試した結果greedyや探索では分岐条件が多く、逆に複雑になってしまいました。
なので今回はdynamic programmingを使った回答になります。
注意すべき事:
- *の前の文字は0でも可
- 普通の正規表現ではなく、入力された文字列が入力されたパターンと完全に一致した場合のみtrue、部分一致は認められません。
以下回答です。
public class Solution { public boolean isMatch(String s, String 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]; } }
簡単に説明します。
まずmatch[]を全部falseに置き、matchした部分をtrueに置いていきます。
入力文字列の最後から読み取っていきます。（前から読み込むと*の処理が面倒だからです）
この問題の一番の難点は*の処理ですね。
i番目の文字が*かどうかで処理を分けます。
以外の場合:
一文字ずつマッチングします。p[i]が'.'か、s[i]と一致した場合trueに置きます。
