2018-12-03

今天刷题在找各种资料的时候，发现了以前一些同学当年刷题准备的时候都写过blog，觉得这个确实是个不错的tool去record并且整理一些事情。现在我也确实处在一个关键的时间点上，就每天来写一点东西记录一下今天的准备和心得吧。Go fight！

LeetCode Wildcard Matching

这题肯定是可以用DP解决的，但是参考了一下各种解法，其实Backtracking 还有贪心都是潜在的解决方案。

先从Greedy + Iteration 开始吧
首先 '?' match and only match one character 或者两个String的character都相等，这时两个都会移动一格
其次处理 ' * ', 由于它可以match any length string or empty string 所以这里要涉及到backtracking, 但由于这个是独立情况，所以可以单独处理，这里使用了 two pointers 来回溯，star是p的 ' * ' index，match是s match的index。

class Solution {
    public boolean isMatch(String s, String p) {
        int ss = 0;
        int pp = 0;
        int star = -1;
        int match = -1;
        
        while (ss < s.length()) {
            if (pp < p.length() && p.charAt(pp) == '?') {
                ss++;
                pp++;
            }else if (pp < p.length() && p.charAt(pp) == s.charAt(ss)) {
                ss++;
                pp++;                
            }else if (pp < p.length() && p.charAt(pp) == '*') {
                star = pp;
                match = ss;
                pp++;
            }else if (star != -1) {
                pp = star + 1;
                match++;
                ss = match;
            }else {
                return false;
            }
        }
        
        while (pp < p.length()) {
            if (p.charAt(pp) == '*') {
                pp++;
            }else {
                return false;
            }
        }
        return true;
    }
}

DP 解法 （未完待续）