一、正则匹配

我一开始想到的是使用正则匹配的方式去做。

* 按题意用正则表示则是[0-9a-z]*。

？按题意用正则表示则是[0-9a-z]。

另外特殊字符.，需要前面加上\\进行转移，这样把匹配串转化成了一个正则匹配串，就可以之间用String的方法直接获取结果。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String pattern = in.nextLine().toLowerCase();
            String s = in.nextLine().toLowerCase();

            char[] chars = pattern.toCharArray();
		  //sb就是正则匹配字符串
            StringBuilder sb = new StringBuilder();
		  //这个用来合并多个连续的*
             char lastc = ' ';
            for (int i = 0; i < chars.length;i++) {
                char c = chars[i];
                if (i != 0){
                    lastc = chars[i-1];
                }
                if (c == '*' ){
                    if (lastc != '*'){
                        sb.append("[0-9a-z]*");
                    }
                    continue;
                }
                if (c == '?'){
                    
                        sb.append("[0-9a-z]");
                
                   
                    continue;
                }
                if (c == '.'){
                    sb.append("\\.");
                    continue;
                }
                sb.append(c);
            }

            System.out.println(s.matches(sb.toString()));

        }
    }
}

二、动态规划

这个可以看看我之前两串最大子串的那个题解https://www.nowcoder.com/feed/main/detail/f952886975314dea8eafa66de153caa5

这题类似，首先定义dp[i][j]，表示待匹配的字符串S的前i个字符组成的子串，和匹配串P的前j个字符组成的子串，之间的匹配状态。用true表示匹配成功。

由简至繁，i的数值是从1到S的长度值，j的数值范围是1到P的长度值，我们需要找出从1->length变化的规律。因为是判断S满不满足P的形式，我们先确定S,再动P。那么对每个场景的遍历方式为：

for (int i = 1; i <= s.length ; i++) {
  for (int j = 1; j <= p.length; j++) {
	//这里就是处理：S的前i个字符，和P的前j个字符的匹配结果
  }
}

循环体中的每个场景下，p的第j个字符p[j-1] (注意索引是0开始，所以要-1)都会遇到什么情况呢？就三种。

1、为通配符*

这个情况下，一是不匹配任何字符，直接把当前p的第j个字符忽略掉，那么dp[i][j]的值就取决于dp[i][j-1]；

二是匹配字符，那么就需要把匹配的S的第i个字符忽略掉，dp[i][j]的值就取决于dp[i-1][j]，但这需要有一个前提，就是S的第i个字符是字母或数字。

所以：dp[i][j] = dp[i][j-1] || （ s[i-1] = 字母或数字 && dp[i-1][j] ）

2、为通配符？

当P第j个字符是？，那S想要匹配就必须是字母或数字，然后匹配上了，还要求S的前i-1个字符与P的前j-1个字符需要匹配。

所以： dp[i][j] = s[i-1] = 字母或数字 && dp[i-1][j]

3、为非通配符

这个是最好处理的，直接比较，但是需要注意忽略大小写,这个需要注意，我是先转成了小写统一比较

所以：dp[i][j] = (s[i-1] == p[j-1]) && dp[i-1][j-1]

for (int i = 1; i <= s.length ; i++) {
	for (int j = 1; j <= p.length; j++) {
		if (p[j - 1] == '*'  ) {
			//当匹配字符为*时，那么要不匹配：dp[i][j] = dp[i][j - 1]，
			//或者匹配字符，但是前字符必须是字母或数字才可以
			dp[i][j] = dp[i][j - 1] || 
			  ( (Character.isLetter(s[i - 1]) || Character.isDigit(s[i - 1])) && dp[i - 1][j]) ;
		} else if (p[j - 1] == '?' ) {
			//如果是？,那么匹配的字符首先要是字母或数字，然后出去匹配的字符，前面的字符要能匹配
			dp[i][j] =  (Character.isLetter(s[i - 1]) || 
						 Character.isDigit(s[i - 1])) && dp[i - 1][j - 1] ;
		} else {
			//如果是其它字符，那忽略大小写，需要相等才能匹配成功
			dp[i][j] = Character.toLowerCase(s[i - 1]) == Character.toLowerCase(p[j - 1]) 
			  && dp[i - 1][j - 1];
		}
	}
}

这里有一个可能会有问题的就是：当p的第j个字符为*时，它转移方程是：

dp[i][j] = dp[i][j-1] || （ s[i-1] = 字母或数字 && dp[i-1][j] ）

假设没有字母或数字的要求，*可以匹配任意一个字符，那么可以匹配0个，1个，2个。。。。。一直到匹配k个字符，可以为1到S长度直接的任意值。它的转移方程应当是：

dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i-2][j] ....................dp[i-k][j]

这样子好像更符和我们思考的方式，匹配多个，但是用的动态规划，其实后面那个dp[i-k][j]是处理过的。就上面那个公式后面一部分【dp[i-1][j] || dp[i-2][j] ....................dp[i-k][j] 】可以直接表示为dp[i-1][j],因为我们在算dp[i-1][j]的时候，按上面的公式会算上【dp[i-1][j] || dp[i-2][j] ....................dp[i-k][j] 】。