My DFA(deterministic finite automata) java codes


  • 6
    J

    regular expression is the expression of regregular language, and regregular language can be expressed by a DFA. I notice that nothing about DFA is talked about in the discuss,so I think I should post my codes to raise this topic.

    During building the DFA, there's a small trick to make the code clean.
    enter image description here

    import java.util.List;
    import java.util.ArrayList;
    
    public class Solution {
        String input;
        public boolean isMatch(String s, String p) {
            input=s;
            
            //----------building DFA------------
            Node start=new Node();
            Node pre=start;
            
            int i=0;
            while(i<p.length()){
                if(i+1<p.length() && p.charAt(i+1)=='*'){
                    Node n1=new Node();
                    Node n2=new Node();
                    pre.addEdge(new Edge(null,n1));
                    pre.addEdge(new Edge(null,n2));
                    n1.addEdge(new Edge(p.charAt(i),n1));
                    n1.addEdge(new Edge(p.charAt(i),n2));
                    pre=n2;
                    i+=2;
                }
                else{
                    Node n=new Node();
                    pre.addEdge(new Edge(p.charAt(i),n));
                    pre=n;
                    i++;
                }
            }
            pre.isEnd=true;
            
            //----------walking DFA-------------
            
            return walk(start,0);
        }
        
        private boolean walk(Node n,int begin){
            if(begin==input.length()){
                if(n.isEnd) return true;
                else if(n.edges.size()==0) return false;
            } 
                
            for(Edge e:n.edges){
                if(e.take==null) {if(walk(e.to,begin)) return true;}
                else if(begin<input.length() && e.take=='.') {if(walk(e.to,begin+1)) return true;}
                else{
                    if(begin<input.length() && e.take==input.charAt(begin)) {if(walk(e.to,begin+1)) return true;}
                    else continue;
                }
            }
            return false;
        }
        
        //-------------below are just some datastruct to implement DFA-------------
        
        private class Node{
            List<Edge> edges;
            boolean isEnd;
            
            Node(){
                edges=new ArrayList<Edge>();
            }
            
            void addEdge(Edge e){
                this.edges.add(e);
            }
        }
        
        private class Edge{
            Character take;
            Node to;
            
            Edge(Character c,Node n){
                this.take=c;
                this.to=n;
            }
        }
    }
    

  • 0
    Q

    Good idea, what is the small trick?


  • 1
    T

    It seems like a NFA.


  • 0
    D

    where is the trick?


  • 0
    D

    @jackjlc DFA is a good idea. Just curious, in my understanding, this means dfs on the DFA graph. Will your solution cause stack overflow? Because dfs brute force visits the graph, since we don't know how many "a" the star * should match, we have try every possibility.

    By the way, I think DP solution solved the stack overflow problem very well.


  • 0
    A

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.