Wildcard Matching

Implement wildcard pattern matching with support for?'?'and?'*'.

• '?'?Matches any single character.
• '*'?Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 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

?

SOLUTION:

通配符匹配，很像Distinct Subsequences的思維方式。像這樣給倆字串，然后看true or false的，基本DP可以用。既然給了倆字傳，那就先不考慮優化問題，先開個二維空間記錄結果。

狀態：f(i , j) 表示S前i個跟T前j個可以不可以匹配。

方程：情況1. T(j) == ? || T(j) == S(i) （因為這兩種情況都是匹配一個字符，所以放在一起）這時候 f(i, j) = f(i - 1, j - 1)。就是說T(j)必須去匹配，不然這個字母沒意義了。

? ? ? ? ?情況2. T(j) == *，這時候＊匹配任意字符，所以呢，f(i, j ) =f(i, j - 1) || f(i - 1, j - 1) || f(i - 2, j - 1) || f(i - 3, j - 1) ... ... || f(1, j - 1):意思就是說，S(i) 之前包括S(i)本身，只要有任意一個跟T(*)前面的一個字符匹配上，就可以。

　　 ? 看起來很麻煩，但是，仔細看，這個公式可以簡化：因為f(i - 1, j) = f(i - 1, j - 1) || f(i - 2, j - 1) || ... ... || f(1, j - 1)， 所以上面f(i , j) ?= f(i , j - 1) || f ( i - 1, j) 。

　　　通俗的說，就是，在當時這一dp層去考慮，我可以用＊匹配 f (i - 1, j) ，也可以不用＊去匹配 f (i, j - 1)。

初始化：f(0, 0 )用方程推不出，所以要單獨考慮。 f（0，0） ＝ true 意思就是null匹配null。

代碼如下：

public class Solution {/*** @param s: A string * @param p: A string includes "?" and "*"* @return: A boolean*/// f(i, j) if p(j) = ? || p(j) == s(i) ==>f(i,j) = f(i - 1, j - 1)// if p(j) = * ==> f(i,j) = f(i - 1, j) f(i, j - 1)public boolean isMatch(String s, String p) {if (s == null){return p == null;}if (p == null){return s == null;}boolean[][] result = new boolean[s.length() + 1][p.length() + 1];result[0][0] = true;for (int i = 1; i <= s.length(); i++){for (int j = 1; j <= p.length(); j++){if (result[0][j - 1] && p.charAt(j - 1) == '*'){result[0][j] = true;}if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?'){result[i][j] = result[i - 1][j - 1];}if (p.charAt(j - 1) == '*'){result[i][j] = (result[i - 1][j] || result[i][j - 1]);}}}return result[s.length()][p.length()];} } View Code

?

轉載于:https://www.cnblogs.com/tritritri/p/4957759.html

總結

以上是生活随笔為你收集整理的[LintCode] Wildcard Matching的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。