regular expression matching_valid number_parsing techniques(3)

方法二：简化的状态机，广度优先搜索，以p为外层循环。

public class Solution {
    public boolean isMatch(String s, String p) {
        Set<Integer> states = new HashSet<>();
        states.add(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) == *;
            Set<Integer> nexts = new HashSet<>();
            for(int state: states) {
                if (re == .) {
                    if (star) {
                        for(int j=state; j<=s.length(); j++) {
                            nexts.add(j);
                        }
                    } else {
                        nexts.add(state+1);
                    }
                } else {
                    if (star) {
                        for(int j=state; j<=s.length(); j++) {
                            nexts.add(j);
                            if (j<s.length() && s.charAt(j) != re) break;
                        }
                    } else {
                        if (state < s.length() && s.charAt(state) == re) nexts.add(state+1);
                    }
                }
            }
            if (star) i ++;
            states = nexts;
            if (states.isEmpty()) return false;
        }
        return states.contains(s.length());
    }
}

另一种实现，这种实现最简单：

public class Solution {
    public boolean isMatch(String s, String p) {
        Set<Integer> states = new HashSet<>();
        states.add(0);
        char[] sa = s.toCharArray();
        char[] pa = p.toCharArray();
        for(int i=0; i<pa.length; i++) {
            if (pa[i] == *) continue;
            boolean star = i<pa.length-1 && pa[i+1] == *;
            Set<Integer> nexts = new HashSet<>();
            for(int state: states) {
                if (state >= sa.length) {
                    if (star) nexts.add(state);
                } else if (star) {
                    nexts.add(state);
                    for(int j=state; j<sa.length && (pa[i] == . || pa[i] == sa[j]); j++) nexts.add(j+1);
                } else {
                    if (pa[i] == . || pa[i] == sa[state]) {
                        nexts.add(state+1);
                    }
                }
            }
            states = nexts;
        }
        return states.contains(sa.length);
    }
}

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