(Java)LeetCode-44.Wildcard Matching

Implement wildcard pattern matching with support for  '?'  and  '*' .

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

この問題を読み始めたばかりの頃、第10題の簡略化版だと思って、この問題の構想を復習して、書くのは簡単でした.
でもタイムアウト..誰の面接でこんな難題が出たんですか.の最近多くの難題に直面して(2つの文字列の距離、最大値の最小値、最短経路blabla.)、血筋が空になりました
その後、ネット上で一つの構想を見て、遡及アルゴリズムを使った.リンクは次のとおりです. http://www.cnblogs.com/felixfang/p/3708999.html
考え方は(抜粋):
    タイムアウトの原因は、レコード付き再帰を使用しても、p上の各'*'に対して、'*'マッチング後の文字のすべての状況、例えばp="c*ab*c"、s="cddabbac"を考慮する必要がある場合、最初の'*'に遭遇し、pの残りの部分「ab*c」とsの残りの部分「ddabbac」のすべての末尾サブセットマッチングを再帰処理する必要があるからである.つまり、「ab*c」と「ddabbac」、「ab*c」と「dabbac」のマッチング、「ab*c」と「abbac」のマッチング、...、「ab*c」と「c」のマッチング、「ab*c」と「0」のマッチングです.
    2番目の'*'に出会っても、相変わらずです.各'*'は、pの残りの部分がsの残りの部分のすべての末尾サブセットと一致することを意味する.しかし,よく考えてみると,実際にはp中の'*'の数が1つより大きい場合,すべての末尾サブセットを上のように一致させる必要はない.
    依然として p=「c*ab*c」、s=「cddabbac」を例に挙げます.
    p=「c*ab*c」の場合、一致できるsは「c.....ab.....c」となり、省略記号は0から任意の文字を表すべきであると推測できる.主にpの真ん中の「ab」が面倒で、必ずsの「ab」をマッチングしなければならないことを発見しました.そのため、sの真ん中に「ab」が存在すれば、すべては後ろの「*」に任せることができます.
    したがって、pとsの文字を1つずつ比較すると、pの最初の'*'に遭遇すると、実際にはsの残りの部分で'ab'と一致する部分を絶えず探す必要があります.
    すなわち、*に遭遇したときのpとsの位置をprespとpressとして記録し、その後、*(++p)と*(++s)を1つずつ比較し続けることができる.*p!=*s,遡って,p= presp,s = press+1,++press;最後まで比較したり、次の'*'に出会ったりして、次の'*'に出会ったら、「ab」の部分が終わったことを説明して、次は2番目の'*'に渡します.pとsが最後になったらtrueを返します.末尾になって新しい'*'に出会っていないし、一致しない値も存在し、pressも末尾になったらfalseに戻ります.
    このような考え方は上の再帰に比べて、最大の違いは:
    '*',我々は次の'*'に遭遇する前のサブ問題だけを考慮し,最後までサブ問題を考慮しない.これにより,大量のサブ問題計算が回避される.
    私たちは記録を通じて prespとpressは,遡及するたびに再帰を避ける方法である.
しかし彼はC++で书いたので、その考えを読んでから、Javaバージョンに书いて、AC、コードは以下の通りです.

public class Solution {
    public boolean isMatch(String s, String p) {
    	int is = 0;
    	int ip = 0;
    	
    	int press = 0;
    	int presp = 0;
    	
    	boolean backstrack = false;
    	for( is = 0; is < s.length(); ){
    		if( ip == p.length()){
    			if(backstrack == false){
    				return false;
    			}else if(p.charAt(p.length()-1) == '*'){
    				return true;
    			}
    			else {
    				ip = presp;
    				is = ++press;
    			}
    		}
    		if(p.charAt(ip) == '?'){
    			is++;
    			ip++;
    		}else if(p.charAt(ip) == '*'){
    			presp = ++ip;
    			press = is;
    			backstrack = true;
    		}else{
    			if(p.charAt(ip) == s.charAt(is)){
    				is++;
        			ip++;
    			}else if(backstrack){
    				ip = presp;
    				is = ++press;
    			}else{
    				return false;
    			}
    		}
    	}
    	while(ip <= p.length() - 1 && p.charAt(ip) == '*' ){
    		ip ++;
    		if( ip == p.length()){
    			break;
    		}
    	}
    	return ip == p.length();
    }
    
    public static void main(String[] args){
    	Solution sol = new Solution();
    	System.out.println(sol.isMatch("aa", "a"));
    	System.out.println(sol.isMatch("aa", "aa"));
    	System.out.println(sol.isMatch("aaa", "aa"));
    	System.out.println(sol.isMatch("aa", "*"));
    	System.out.println(sol.isMatch("aa", "a*"));
    	System.out.println(sol.isMatch("ab", "?*"));
    	System.out.println(sol.isMatch("aab", "c*a*b"));
    	System.out.println(sol.isMatch("ab", "*a"));
    	System.out.println(sol.isMatch("hi", "*?"));
    }
}