[Leetcode] Regular Expression Matching State Machine.java

public class Solution {
    class State {
        boolean end;
        Map<Character, List<State>> transferTable;
        State() {
            transferTable = new HashMap<>();
        }
        
        void addTransfer(char c, State next) {
            if (transferTable.containsKey(c)) {
                transferTable.get(c).add(next);
            } else {
                List<State> nexts = new ArrayList<>();
                nexts.add(next);
                transferTable.put(c, nexts);
            }
        }
        
        List<State> getNext(char c) {
            return transferTable.get(c);
        }
        
        void setEnd() {
            end = true;
        }
        
        boolean isEnd() {
            return end;
        }
    }
    
    State compile(String pattern) {
        State root = new State();
        State cur = root;
        for (int i = 0; i < pattern.length(); i++) {
            if (i < pattern.length() - 1 && '*' == pattern.charAt(i + 1)) {
                cur.addTransfer(pattern.charAt(i), cur);
                State next = new State();
                cur.addTransfer('\0', next);
                cur = next;
                i++;
            } else {
                State next = new State();
                cur.addTransfer(pattern.charAt(i), next);
                cur = next;
            }
        }
        cur.setEnd();
        return root;
    }
    
    boolean isMatch(String input, int index, State cur) {
        if (index == input.length() && cur.getNext('\0') == null) {
            return cur.isEnd();
        }
        if (index < input.length() && cur.getNext(input.charAt(index)) != null) {
            for (State next : cur.getNext(input.charAt(index))) {
                if (isMatch(input, index + 1, next)) {
                    return true;
                }
            }
        }
        if (cur.getNext('\0') != null) {
            for (State next : cur.getNext('\0')) {
                if (isMatch(input, index, next)) {
                    return true;
                }
            }
        }
        if (index < input.length() && cur.getNext('.') != null) {
            for (State next : cur.getNext('.')) {
                if (isMatch(input, index + 1, next)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean isMatch(String s, String p) {
        return isMatch(s, 0, compile(p));
    }
}

[Leetcode] Regular Expression Matching.java

public class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, 0, p, 0);
    }
    
    public boolean isMatch(String input, int inputIndex, String pattern, int patternIndex) {
        if (inputIndex == input.length() && patternIndex == pattern.length()) {
            return true;
        } else if (patternIndex == pattern.length()) {
            return false;
        }
        char curPat = pattern.charAt(patternIndex);
        if (patternIndex < pattern.length() - 1 && '*' == pattern.charAt(patternIndex + 1)) {
            if ('.' == curPat) {
                for (int i = inputIndex; i <= input.length(); i++) {
                    if (isMatch(input, i, pattern, patternIndex + 2)) {
                        return true;
                    }
                }
            } else {
                if (isMatch(input, inputIndex, pattern, patternIndex + 2)) {
                    return true;
                }
                for (int i = inputIndex; i < input.length(); i++) {
                    if (input.charAt(i) == curPat) {
                        if (isMatch(input, i + 1, pattern, patternIndex + 2)) {
                            return true;
                        }
                    } else {
                        break;
                    }
                }
            }
        } else {
            if ('.' == curPat) {
                return isMatch(input, inputIndex + 1, pattern, patternIndex + 1);
            } else {
                return inputIndex < input.length() 
                    && input.charAt(inputIndex) == curPat && isMatch(input, inputIndex + 1, pattern, patternIndex + 1);
            }
        }
        return false;
    }
}