regular expression matching_valid number_parsing techniques(5)

方法三：广度优先搜索，简化的自动机，外层循环是s

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

方法四：动态规划，以p为外层循环。

public class Solution {
    public boolean isMatch(String s, String p) {
        char[] sa = s.toCharArray();
        char[] pa = p.toCharArray();
        boolean[] match = new boolean[sa.length + 1];
        match[0] = true;
        for(int i = 1; i <= pa.length; i++) {
            boolean[] next = new boolean[sa.length + 1];
            if (i < pa.length && pa[i] == *) {
                for(int j = 0; j <= sa.length; j++) {
                    if (match[j] || (j > 0 && next[j - 1] && (pa[i - 1] == . || pa[i - 1] == sa[j - 1]))) {
                        next[j] = true;
                    }
                }
                i++;
            } else {
                for(int j = 1; j <= sa.length; j++) {
                    if (match[j - 1] && (pa[i - 1] == . || pa[i - 1] == sa[j - 1])) {
                        next[j] = true;
                    }
                }
            }
            match = next;
        }
        return match[sa.length];
    }
}

方法五：动态规划，以s为外层循环。regular expression matching

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