Wildcard Matching 192
Question
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", "cab") → false
Solution
DP解法:
result[i][j]表示S的前i个字符能否和T的前j个字符匹配。
初始化:result[0][j]=result[0][j-1] && T.charAt(j-1)=='',即只有‘’才可能和空字符匹配
状态函数:
if T.charAt(j-1)=='?'||S.charAt(i-1)==T.charAt(j-1)
result[i][j]=result[i-1][j-1]
if T.charAt(j-1)=='*'
result[i][j]=result[i-1][j]||result[i][j-1]
情况1. T(j) == ? || T(j) == S(i) 这时候 f(i, j) = f(i - 1, j - 1)。就是说T(j)必须去匹配,不然这个字母没意义了。
情况2. T(j) == ,此时分为两种情况。第一种情况让T(j)的 和S(i)匹配,所以看result[i - 1][j]的值(j匹配完还在因为 可以匹配任意字符; 第二种情况不让T(j)和S(i)匹配(也可以看成匹配为空字符),此时看result[i][j - 1]的值。两种情况只要有只要有之只要有一种为true,则result[i][j]则责=true。
双指针解法:
实质是贪心算法: whenever encounter ‘’ in p, keep record of the current position of ‘’ in p and the current index in s. Try to match the stuff behind this ‘*’ in p with s, if not matched, just s++ and then try to match again.
指针star记录p中遇见的最后一个" "的位置(前面的" "如果没有和s中字符匹配可以认为已经和" "匹配),指针mark记录s中第一个需要和" * "匹配的字符的位置。
开始遍历s和p,如果两个字符匹配(p中字符和s中字符相同或者p中字符为"?"),则i和j同时前进一位。
如果p中字符为" ",则用star记下该位置,用mark记录下此时i的位置,同时j前进一位。可以认为该" "被保留,如果有需要之后可以被拿出来和s中从i位置开始的任意字符进行匹配。
如果p中字符不为1和2中的情况,表明p中字符和s中字符无法匹配,此时需要看是否之前有保留的" "可以使用,如果没有就gg,如果有就将该" "和s中mark位置字符进行匹配,同时将j放回该" "位置后面一位,将mark前进一位,同时将i放到此时mark的位置。" "继续保留,因为" * "可以和任意长度字符匹配,所以在这次匹配之后不会被消耗。
最后如果s遍历完成,而p中还有字符剩余,则看p中剩余字符是否都为" * "
代码如下:
DP version:
public class Solution {
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: A boolean
*/
public boolean isMatch(String s, String p) {
// write your code here
if(s.length() == 0){
for(int i = 0; i < p.length(); i++){
if(p.charAt(i) != '*'){
return false;
}
}
return true;
}
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 j = 1; j <= p.length(); j++){
if(result[0][j - 1] && p.charAt(j - 1) == '*'){
result[0][j] = true;
}
}
for (int i = 1; i <= s.length(); i++){
for (int j = 1; j <= p.length(); j++){
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()];
}
}
Two Pointer version
public class Solution {
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: A boolean
*/
public boolean isMatch(String s, String p) {
// write your code here
if(s.length() == 0){
for(int i = 0; i < p.length(); i++){
if(p.charAt(i) != '*'){
return false;
}
}
return true;
}
if (s == null){
return p == null;
}
if (p == null){
return s == null;
}
int i = 0;
int j = 0;
int star = -1;
int mark = -1;
while(i < s.length()){
if(j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))){
i++;
j++;
}else if(j < p.length() && p.charAt(j) == '*'){
star = j;
j++;
mark = i;
}else if(star != -1){
j = star + 1;
i = ++mark;
}else{
return false;
}
}
while(j < p.length() && p.charAt(j) == '*'){
j++;
}
return j == p.length();
}
}