通配符匹配

package com.sly.uploadfile.algorithm.pack1;

/**
 * Created by fmgao on 2019/9/12.
 *
 * 示例：
 *      输入:
         s = "aa"
         p = "a"
         输出: false
         解释: "a" 无法匹配 "aa" 整个字符串。
 *
 */
public class TongPeiFuPiPei {

    public static void main(String[] args) {
        boolean res = getTongPei("cb", "?b");
        System.out.println(res);
    }

    public static boolean getTongPei(String s, String p) {
        // 申请dp[][]表格，dp[i][j]表示 若s(0,i-1)与p(0,j-1)匹配，dp[i][j]=true，否则为false
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        // s与p都为空时，匹配
        dp[0][0] = true;
        // s为空,p中含有‘*‘时
        for (int j = 1; j < (p.length() + 1); j++) {
            if (p.charAt(j - 1) == ‘*‘){
                dp[0][j] = dp[0][j - 1] && true;
            }
        }

        for (int i = 1; i < (s.length() + 1); i++) {
            for (int j = 1; j < (p.length() + 1); j++) {
                if ((p.charAt(j - 1) == s.charAt(i - 1)) || (p.charAt(j - 1) == ‘?‘)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if (p.charAt(j - 1) == ‘*‘) {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}