Leet Code44ワイルドカードマッチング-ワイルドカードマッチング-Java



Leet Code 44 Wildcard Matching Wildcard Matching Java



元の問題のリンク https://leetcode.com/problems/wildcard-matching

実装は「?」をサポートしますそして、「*」ワイルドカードパターンマッチング。



「?」任意の1文字に一致します。

'*'任意の文字シーケンス(空を含む)に一致します。



入力文字列全体と一致する必要があります(部分文字列一致セクションだけでなく)。

いくつかの例:

public class Solution { public static boolean isMatch(String s, String p) { boolean[][] dp = new boolean[s.length() + 1][p.length() + 1] dp[0][0] = true for (int j = 0 j

動的計画法を使用する。入力文字列をs、長さm、パターン文字列をp、長さn、ブール配列dp [m + 1] [n +1]に設定します。



dp [0] [j +1]は空の文字列を表しp [0..j]は一致し、dp [i + 1] [j +1]はs [0..i]とp [0..j]を表します]一致します。

p [j] == '*'の場合、dp [i + 1] [j + 1] = dp [i] [j + 1] || dp [i + 1] [j]。

p [j] == '?'の場合|| p [j] == s [i]、dp [i + 1] [j + 1] = dp [i] [j]。

その他の場合dp [i + 1] [j + 1] = false。

isMatch('aa','a') → false isMatch('aa','aa') → true isMatch('aaa','aa') → false isMatch('aa', '*') → true isMatch('aa', 'a*') → true isMatch('ab', '?*') → true isMatch('aab', 'c*a*b') → false

複製:https://my.oschina.net/mistymarch/blog/699506