Wildcard Matching

Wildcard Matching
给定两个字符串p和q，判断两个字符串是否匹配。规则是：‘*’可以代表任意长度的字符串，也可以代表空串；‘?’代表任意单个的字符串。
例如：
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

这是leetcode中一道偏难的题目，我认为它属于LCS的变形，属于二维动态规划的问题。解决它我们主要要分析当前字符能代表什么。既然是二维的动态规划问题，我们创建一个二维的布尔型数组result，如果两个字符串都为空时，返回true，因此result[0][0] = true; 接着我们还要继续初始化数组的第一行，也就是result[0][i]，当wildcard的当前字符为‘*’时，result[0][i]= true;当遇到不为’*'我们终止数组的初始化。

接下来我们找出状态转移方程。如果当然字符为’*‘时，我们即可以把它当做空字符也可以让它代替待匹配字符串的从当前字符开始到后面所有的字符，因此此时的动态转移方程为：result[i][j] = result[i - 1][j] || result[i][j - 1]，(cur == '*')；如果当前字符不为’*'时，如果cur等于待匹配字符串的当前字符或者cur等于’?‘时它们就可以匹配，与此同时，我们还要考虑上一个状态，当(cur != '*') 时的递推式为：result[i][j] = result[i - 1][j - 1] && (cur == '?' || cur == s.charAt(i - 1))。

有了初始化和递推式，代码就写出来了，代码如下：

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] result = new boolean[m + 1][n + 1];
        result[0][0] = true;
        for(int i = 1; i <= n; i++) {
            if(p.charAt(i - 1) == '*')
                result[0][i] = true;
            else
                break;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                char cur = p.charAt(j - 1);
                if(cur != '*') {
                    result[i][j] = result[i - 1][j - 1] && (cur == '?' || cur == s.charAt(i - 1));
                } else {
                    result[i][j] = result[i - 1][j] || result[i][j - 1];
                }
            }
        }
        return result[m][n];
    }
}