wildcard_overflow.java

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        return helper(s, 0, p, 0, new HashMap<List<Integer>, Boolean>());
    }
    public boolean helper(String s, int sstart, String p, int pstart, Map<List<Integer>, Boolean> dp) {
        if (pstart >= p.length()) {
            return false;
        }
        boolean rst = false;
        if (dp.containsKey(Arrays.asList(sstart, pstart))) {
            return dp.get(Arrays.asList(sstart, pstart));
        }
        if (sstart >= s.length()) {
            rst = pstart >= p.length() || (p.charAt(pstart)=='*' && helper(s, sstart, p, pstart+1, dp));
            dp.put(Arrays.asList(sstart, pstart), rst);
            return rst;
        }
        char pch =  p.charAt(pstart);
        if (pch == '*') {
            rst = helper(s, sstart+1, p, pstart, dp) || helper(s, sstart, p, pstart+1, dp);
        } else if (pch == '?') {
            rst = sstart<s.length() && helper(s, sstart+1, p, pstart+1, dp);
        } else {
            rst = sstart<s.length() && s.charAt(sstart)==pch && helper(s, sstart+1, p, pstart+1, dp);
        }
        dp.put(Arrays.asList(sstart, pstart), rst);
        return rst;
    }
}