regular expression matching_valid number_parsing techniques(2)

另一种实现：

public class Solution {
/*
"aa"
"a"
"aa"
"a*"
"aa"
"aaa"
"aa"
".*"
"a"
"ab*"
"a"
".*..a*"
*/
    public boolean isMatch(String s, String p) {
        NFA nfa = new NFA();
        Integer start = nfa.addState();
        Integer accept;
        Integer current = start;
        for(int i=0; i<p.length(); i++) {
            if (i<p.length()-1 && p.charAt(i+1) == *) {
                Integer next = nfa.addState();
                nfa.addNext(current, null, next);
                nfa.addNext(next, p.charAt(i), next);
                i++;
                current = next;
            } else {
                Integer next = nfa.addState();
                nfa.addNext(current, p.charAt(i), next);
                current = next;
            }
        }
        accept = current;
        // nfa.print();
        Set<Integer> states = new HashSet<>();
        states.add(0);
        states = nfa.getClosure(states);
        // System.out.printf("Begins, states=%s\n", states);
        for(int i=0; i<s.length(); i++) {
            Set<Integer> nexts = nfa.getNexts(states, s.charAt(i));
            states = nfa.getClosure(nexts);
        }
        return states.contains(accept);
    }
}
class NFA {
    private Map<Integer, Map<Character, Set<Integer>>> transfers = new HashMap<>();
    void print() {
        for(Integer state: transfers.keySet()) {
            Map<Character, Set<Integer>> transfer = transfers.get(state);
            for(Character ch: transfer.keySet()) {
                System.out.printf("[%s]--%s-->%s\n", state, ch, transfer.get(ch));
            }
        }
    }
    
    int states = 0;
    Integer addState() {
        return states++;
    }
    
    void addNext(Integer state, Character ch, Integer next) {
        Map<Character, Set<Integer>> transfer = transfers.get(state);
        if (transfer == null) {
            transfer = new HashMap<Character, Set<Integer>>();
            transfers.put(state, transfer);
        }
        Set<Integer> nexts = transfer.get(ch);
        if (nexts == null) {
            nexts = new HashSet<>();
            transfer.put(ch, nexts);
        }
        nexts.add(next);
    }
    
    Set<Integer> getClosure(Set<Integer> states) {
        Set<Integer> closure = new HashSet<>();
        closure.addAll(states);
        Set<Integer> currents = states;
        boolean found;
        do {
            found = false;
            currents = getNexts(currents, null);
            for(Integer state: currents) {
                if (!closure.contains(state)) {
                    closure.add(state);
                    found = true;
                }
            }
        } while (found);
        return closure;
    }
    Set<Integer> getNexts(Set<Integer> states, Character ch) {
        Set<Integer> results = new HashSet<>();
        for(Integer state: states) {
            Map<Character, Set<Integer>> transfer = transfers.get(state);
            if (transfer == null) continue;
            Set<Integer> nexts;
            if (ch == null) {
                nexts = transfer.get(ch);
                if (nexts == null) continue;
            } else {
                nexts = new HashSet<Integer>();
                Set<Integer> chnext = transfer.get(ch);
                if (chnext != null) nexts.addAll(chnext);
                Set<Integer> dot = transfer.get(.);
                if (dot != null) nexts.addAll(dot);
            }
            results.addAll(nexts);
        }
        return results;
    }
}

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