Regular Expression Matching NFA.java

public class Solution {
    
    private class Graph {
            
            private int V;
            private int E;
            private ArrayList<Integer>[] adj;
            private boolean[] visited;
            
            public Graph(int V) {
                adj = (ArrayList<Integer>[])new ArrayList[V];
                visited = new boolean[V];
                this.V = V;
                E = 0;
                
                for(int i = 0; i < V; ++i){
                    adj[i] = new ArrayList<Integer>();
                }
            }
            
            public void addEdgeFromTo(int v, int w) {
                adj[v].add(w);
                E++;
            }
            
            public boolean visited(int v) {
                return visited[v];
            }
            
            public void dfs(int v) {
                visited[v] = true;
                for(int w : adj(v)) {
                    if(!visited[w])
                        dfs(w);
                }
            }
            
            public void reset() {
                for(int i = 0; i < V; ++i){
                    visited[i] = false;
                }
            }
            
            public ArrayList<Integer> adj(int v) {
                return adj[v];
            }
            
            public int V() {
                return V;
            }
            
            public int E() {
                return E;
            }
        }
        
        private char[] reg;
        private int M;
        private Graph G;
    
    
    public boolean isMatch(String s, String p) {
        
        int len = p.length();
        reg = p.toCharArray();
        G = new Graph(len + 1);
        M = len;
        
        for(int i = 0; i < M; ++i){
            if(i < M - 1 && reg[i + 1] == '*'){
                G.addEdgeFromTo(i, i + 1);
                G.addEdgeFromTo(i + 1, i);
            }
            if(reg[i] == '*'){
                G.addEdgeFromTo(i, i + 1);
            }
        }
        
        ArrayList<Integer> pc = new ArrayList<Integer>();
        G.dfs(0);
        for(int i = 0; i < G.V(); ++i){
            if(G.visited(i))
                pc.add(i);
        }
        
        for(int i = 0; i < s.length(); ++i){
            ArrayList<Integer> newpc = new ArrayList<Integer>();
            for(int v : pc) {
                if(v < M && (reg[v] == s.charAt(i) || reg[v] == '.')){
                    newpc.add(v + 1);
                }
            }
            
            G.reset();
            for(int v : newpc) {
                G.dfs(v);
            }
            
            for(int j = 0; j < G.V(); ++j){
                if(G.visited(j))
                    newpc.add(j);
            }
            
            pc.clear();
            pc = newpc;
        }
        
        for(int v : pc) {
            if(v == M)
                return true;
        }
        
        return false;
    }
}