原题链接在这里：https://leetcode.com/problems/wildcard-matching/
采用双指针，i为s的index, j为p的index.
若是当前对应字符match, 双双后移一位。若是不能match且p的当前字符是‘*‘, 就更新星号的starIndex 和 最后检查的位置lastCheck.
当再次遇到不match时，j回到startIndex的后一位，lastCheck后一一位，i到lastCheck位上。
出了while loop 说明s到头了，看j是否到头即可。但是若当前j是‘*‘, 需要一致后移j.
Time Complexity is O(s.length() * p.length()). Space is O(1).
AC Java:
public class Solution { public boolean isMatch(String s, String p) { if(p.length() == 0){ return s.length() == 0; } int starIndex = -1; //标记星号的index int lastCheck = -1; //标记上次检查的位置 int i = 0; int j = 0; while(i<s.length()){ if(j<p.length() && isMatch(s.charAt(i), p.charAt(j))){ i++; j++; }else if(j<p.length() && p.charAt(j) == ‘*‘){ starIndex = j; lastCheck = i; j++; }else if(starIndex != -1){ j = starIndex+1; lastCheck++; i=lastCheck; }else{ return false; } } //s = "", p = "**" while(j<p.length() && p.charAt(j) == ‘*‘){ j++; } return j == p.length(); } private boolean isMatch(char s, char p){ return p == ‘?‘ || s == p; } }
Ref: http://www.cnblogs.com/icecreamdeqinw/p/4324962.html
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4952497.html