通配符匹配

public class Solution {
    public boolean isMatch(String s, String p) {
        // 动态规划：需要O(s.length()*p.length())的额外数组空间
        int lenS = s.length();
        int lenP = p.length();
        boolean[][] dp = new boolean[lenS+1][lenP+1];        // dp[i][j]表示s的前i个字符串和p的前j个字符串是否匹配
        dp[0][0] = true;
        // 初始化base case
        // dp[i][0]一定为false，无需初始化（i>0）
        // 如果p.substring(0,j)中只包含*，那么dp[0][j]为true
        for(int j=1; j<=lenP; j++) {
            if (p.charAt(j-1) == '*') {
                dp[0][j] = dp[0][j-1];
            } else {
                dp[0][j] = false;
            }
        }
        for(int i=1; i<=lenS; i++) {
            for(int j=1; j<=lenP; j++) {
                char charP = p.charAt(j-1);
                char charS = s.charAt(i-1);
                if (charP == charS || charP == '?') { // 如果p[j]是非通配符，那么s[i]必须为相同字母，并且dp[i][j]取决于dp[i-1][j-1]
                    dp[i][j] = dp[i-1][j-1];
                } else if (charP == '*') { // 如果p[j]是*，那么dp[i][j]的状态等于dp[i-1][j]或不考虑*：dp[i][j-1]
                    dp[i][j] = dp[i-1][j] | dp[i][j-1];
                }
            }
        }
        return dp[lenS][lenP];
    }
}

public class Solution {
    public boolean isMatch(String s, String p) {
        // 贪心+回溯+双指针，只需O(1)的空间
        // 贪心体现在哪?：能进行字符匹配，就绝不用*匹配，并且*尽量匹配少的字符(0~n)。这样的贪心可以保证每一种可能的匹配方式都考虑到
        int i = 0;      // s的移动指针
        int j = 0;      // p的移动指针
        int pi = -1;    // s处理通配符*的回溯指针
        int pj = -1;    // p处理通配符*的回溯指针
        int lenS = s.length();
        int lenP = p.length();
        while(i < lenS) {
            if (j<lenP && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) { // 如果是字符匹配 或是 ?匹配，则指针后移，无需考虑回溯指针
                i++;
                j++;
            } else if (j < lenP && p.charAt(j) == '*') { // 如果是*匹配，则指针仍然后移，但此时需要标记回溯指针。如果后续发现*匹配的字符数少了，需要通过回溯指针回溯处理
                pi = i;        // 注意此时i指针不后移，因为*可以匹配0~n个字符；如果i后移了，则表示*无法匹配0个字符
                pj = j++;
            } else if (pi >= 0) { // 此时发现匹配不上或者p字符串已经处理完，则考虑通过回溯指针回溯，从而使得p中的通配符*多匹配一些字符
                i = ++pi;        // 让p中的*通配符在s中多匹配一个字符
                j = pj+1;        // j回到p中*通配符的下一个字符
            } else { // 如果既无法匹配，又无法回溯，那么匹配失败
                return false;
            }
        }
        // 如果s字符串处理完，但p还未处理完
        for(; j<lenP; j++) {
            if (p.charAt(j) != '*') {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();
        boolean[][]dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=0;i<n;i++){
            if(p.charAt(i)=='*') dp[0][i+1]=true;
            else break;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(Character.isLetter(p.charAt(j-1))){
                    dp[i][j]= ((s.charAt(i-1)==p.charAt(j-1)&&dp[i-1][j-1]));
                }else if(p.charAt(j-1)=='?'){
                    //可以匹配一个
                    dp[i][j]=dp[i-1][j-1];

                }else{
                    //当为*
                    for(int k=0;k<=m;k++){
                        if(dp[k][j-1]){
                            dp[i][j]=true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[m][n];
    }
}

import java.util.*;

public class Solution {
    public boolean isMatch(String s, String p) {
        return dp(s , p , s.length(), p.length());
    }
    
    HashMap<String,Boolean> memo = new HashMap<>();
    
    public boolean dp(String str, String pattern,int i, int j){
        int m = str.length();
        int n = pattern.length();
        //base case
        if(i ==0 &&j == 0){
            return true;
        }
        if(i >= 1 && j== 0){
            return false;
        }
     
        
        String key = i + "," + j ;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        
        boolean res = false;
        if(pattern.charAt(j -1 )!= '*'){
            if(i > 0){
                boolean one = str.charAt(i - 1) == pattern.charAt(j - 1);
                boolean two = pattern.charAt(j - 1) == '?';
                if(one || two){
                    res = dp(str, pattern , i-1, j-1);
                }
            }
        }else{
            if (i >= 1 && j >= 1) {
                res = dp(str, pattern, i - 1, j - 1);
            }
            if (i >= 1) {
                res = res || dp(str, pattern, i - 1, j);
            }
            if (j >= 1) {
                res = res || dp(str, pattern, i, j - 1);
            }
        }
        
           // 将当前结果记入备忘录
        memo.put(key, res);
        return res;
    }
}

public class Solution{
public boolean isMatch(String s, String p) {
    //初始化
    int row=s.length();
    int col=p.length();
    boolean[][] dp=new boolean[row+1][col+1];
    //对于p为空，不论s为什么(除s也为空外，dp均为false
    //对于s为空
    dp[0][0]=true;
    for(int j=1;j<col+1;j++){
        if(dp[0][j-1]){
            if(p.charAt(j-1)=='*'){
                dp[0][j]=true;
            }
            else
                break;
      }
    }
    //接下来遍历dp数组,s--row,p--col
    for(int i=1;i<row+1;i++){
        for(int j=1;j<col+1;j++){
            if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='?')
                dp[i][j]=dp[i-1][j-1];
            if(p.charAt(j-1)=='*')
                //也可以这么写，但其实只要dp[i][j]为真，那么dp[i+1][j]一定为真，也就说dp[i][j]其实已经呗dp[i+1][j]包含了
                //dp[i + 1][j + 1] = dp[i][j] || dp[i + 1][j] || dp[i][j + 1];
                dp[i][j]=dp[i-1][j]||dp[i][j-1];
        }
    }
    return dp[row][col];
}
}

public class Solution {
    public boolean isMatch(String s, String p) {
        // 记忆化搜索
        cache = new int[s.length() + 1][p.length() + 1];
        return check(s.toCharArray(), 0, p.toCharArray(), 0);
    }
    
    private int[][] cache; // 记忆化搜索
    private boolean check(char[] ss, int i, char[] pp, int j) {
        if (cache[i][j] != 0) return cache[i][j] == 1;
        
        // 模式串匹配完，主串是否还有剩余
        if (pp.length == j) {
            cache[i][j] = ss.length == i ? 1 : -1;
            return ss.length == i;
        }
        // 主串匹配完，模式串要么没有剩余，要么剩下的全是*
        if (ss.length == i) {
            while (j < pp.length && pp[j] == '*') j++;
            cache[i][j] = j == pp.length ? 1 : -1;
            return j == pp.length;
        }
        
        boolean match = false;
        if (pp[j] == '*') {
            match = check(ss, i, pp, j + 1) || check(ss, i + 1, pp, j);
        } else if (i < ss.length && (pp[j] == '?' || ss[i] == pp[j])) {
            match = check(ss, i + 1, pp, j + 1);
        }
        
        cache[i][j] = match ? 1 : -1;
        
        return match;
    }
}

    public boolean isMatch(String s, String p) {
        // len_s：s 的长度； index_s ： 当前 s 的索引； pre_s ：在遇到 * 前的 s 索引，用来恢复 index_s 的值
        int len_s = s.length(), index_s = 0, pre_s = 0;
        int len_p = p.length(), index_p = 0, pre_p = 0;
        boolean flag = false;
        while (index_s < len_s) {
            if (index_p < len_p && ( s.charAt(index_s) == p.charAt(index_p) || p.charAt(index_p) == '?' )) {
                // 正常匹配相等的普通字符或者占位符 "?"
                index_s ++;
                index_p ++;
            }else if (index_p < len_p && p.charAt(index_p) == '*') {
                // 跳过并且记录 * 后面开始匹配时的索引，用于后面的回溯时恢复相应的数据
                pre_p = (++index_p);
                pre_s = index_s;
                flag = true;
            }else {
                // 上面的内容无法匹配时，来到这里。如果前面出现过 * ，则恢复相应的数据； 否则， 直接返回 false
                if (flag) {
                    /*
                    回溯法， 恢复数据，
                    进入下一层可能取值
                     */
                    index_p = pre_p;
                    // p 的* 多匹配一个 s 的字符，相当于 * 匹配  0,1,2…… 个 s 的连续字符
                    index_s = (++pre_s);
                }else {
                    return false;
                }
            }
        }
        // 循环掉 p 后面可能带的所有 * 字符
        while (index_p < len_p && p.charAt(index_p) == '*') {
            index_p ++;
        }
        return index_s == len_s && index_p == len_p;
    }

    public static void main(String[] args) {
        WildcardMatching wildcardMatching = new WildcardMatching();
        wildcardMatching.isMatch("aa", "a");
    }

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null||p == null){
            return false;
        }
        int m = s.length()+1;
        int n = p.length()+1;
        //flag[i][j]表示s.length()=i，p.length()=j时的匹配情况
        boolean[][] flags = new boolean[m][n];
        
        /********边界情况********/
        
        //（1）当s.length和p.length都为0时
        flags[0][0]=true;
        //（2）当s.length不为0，p.length都为0时
        for(int i = 1;i< m;i++){
            flags[i][0] = false;
        }
        //（3）当s.length为0，p.length不为0时，只有当p为“*”时，则返回true,否则返回false
        for(int j = 1;j < n;j++){
            if(p.charAt(j-1) == '*'){
                flags[0][j] = flags[0][j-1];
            }
            else{
                flags[0][j] = false;
            }
        }
        
        /************一般情况**********/
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
            //如果相同位置的字符匹配，则继续匹配，flags[i][j]等于s,p各上一个字符匹配情况flags[i-1][j-1]的值
                if(s.charAt(i-1) == p.charAt(j-1)||p.charAt(j-1) == '?'){
                    flags[i][j] = flags[i-1][j-1];
                }
            //如果遍历字符串p，遇到字符为‘*’,则flags[i][j]等于s，p上一次匹配的所有情况的
            //flags[i][j]、flags[i][j-1]、flags[i-1][j]的或操作的结果
                else if(p.charAt(j-1) == '*'){
                    flags[i][j] = flags[i][j]||flags[i-1][j]||flags[i][j-1];
                }
                else{
                    flags[i][j] = false;
                }
            }
        }
        return flags[m-1][n-1];
    }
}

public class WildCardMatching {          public boolean isMatch(String s, String p) {
        int n=s.length();
        int m=p.length();
        boolean [][] dp=new boolean[n+1][m+1];
        dp[n][m]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)=='*'){
                dp[n][i]=true;
            }else{
                break;
            }
        }
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?'){
                    dp[i][j]=dp[i+1][j+1];
                }else if(p.charAt(j)=='*'){
                    dp[i][j]=dp[i+1][j]||dp[i][j+1];
                }else{
                    dp[i][j]=false;
                }
            }
        }
        return dp[0][0];
    }
}
raodanwoyiranxihuanni

I found this solution from http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html

The basic idea is to have one pointer for the string and one pointer for the pattern. This algorithm iterates at most length(string) + length(pattern) times, for each iteration, at least one pointer advance one step.

Here is Yu's elegant solution in C++

bool isMatch(const char *s, const char *p) { const char* star=NULL; const char* ss=s; while (*s){
            //advancing both pointers when (both characters match) or ('?' found in pattern)
            //note that *p will not advance beyond its length if ((*p=='?')||(*p==*s)){s++;p++;continue;} 

            // * found in pattern, track index of *, only advancing pattern pointer if (*p=='*'){star=p++; ss=s;continue;} 

            //current characters didn't match, last pattern pointer was *, current pattern pointer is not *
            //only advancing pattern pointer if (star){ p = star+1; s=++ss;continue;} 

           //current pattern pointer is not star, last patter pointer was not *
           //characters do not match return false;
        }

       //check for remaining characters in pattern while (*p=='*'){p++;} return !*p;  
    }

Here is my re-write in Java

boolean comparison(String str, String pattern) { int s = 0, p = 0, match = 0, starIdx = -1; while (s < str.length()){ // advancing both pointers if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                s++;
                p++;
            } // * found, only advancing pattern pointer else if (p < pattern.length() && pattern.charAt(p) == '*'){
                starIdx = p; match = s;
                p++;
            } // last pattern pointer was *, advancing string pointer else if (starIdx != -1){
                p = starIdx + 1; match++;
                s = match;
            } //current pattern pointer is not star, last patter pointer was not * //characters do not match else return false;
        } //check for remaining characters in pattern while (p < pattern.length() && pattern.charAt(p) == '*')
            p++; return p == pattern.length();
}

public class Solution {
    public boolean isMatch(String s, String p) {
		if(p.length() == 0) {
			if(s.length() == 0) return true;
			else return false;
		}
		boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
		dp[0][0] = true;
		for (int i = 1; i < dp[0].length; i ++ ) { // 处理第一行,注意多个"*"的情况
			if(p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 1];
		}
		for (int i = 1; i < dp.length; i ++ ) {
			for (int j = 1; j < dp[0].length; j ++ ) {
				if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') dp[i][j] = dp[i - 1][j - 1];
				if(p.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
			}
		}
		return dp[dp.length - 1][dp[0].length - 1];
	}
}