regular expression matching_valid number_parsing techniques(4)

另一种实现：

public class Solution {
    /*
    这些case都很重要，很多BUG！！！
""
""
"aa"
"a"
"aa"
"a*"
"aa"
"aaa"
"aa"
".*"
"a"
"ab*"    
*/
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int[] states = new int[n+1];
        int[] nexts = new int[n+1];
        boolean[] reached = new boolean[n+1];
        reached[0] = true;
        int size = 0;
        states[size++] = 0;
        for(int i=0; i<p.length(); i++) {
            char re = p.charAt(i);
            if (re == *) continue;
            boolean star = i<p.length()-1 && p.charAt(i+1) == *;
            Arrays.fill(reached, false);
            int nextSize = 0;
            for(int k=0; k<size; k++) {
                int state = states[k];
                if (re == .) {
                    if (star) {
                        for(int j=state; j<=n; j++) {
                            if (reached[j]) continue;
                            reached[j] = true;
                            nexts[nextSize++] = j;
                        }
                    } else if (state < n && !reached[state+1]) {
                        reached[state+1] = true;
                        nexts[nextSize++] = state+1;
                    }
                } else {
                    if (star) {
                        for(int j=state; j<=s.length(); j++) {
                            if (!reached[j]) {
                                reached[j] = true;
                                nexts[nextSize++] = j;
                            }
                            if (j<n && s.charAt(j) != re) break;
                        }
                    } else {
                        if (state < n && s.charAt(state) == re && !reached[state+1]) {
                            reached[state+1] = true;
                            nexts[nextSize++] = state + 1;
                        }
                    }
                }
            }
            if (star) i ++;
            int[] temp = states;
            states = nexts;
            nexts = temp;
            size = nextSize;
            if (size == 0) return false;
        }
        return reached[n];
    }
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-39693-4.html