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.

```
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;
}
}
}
```