請實作一個函數用來比對包括’.’和’‘的正規表達式。模式中的字元’.’表示任意一個字元，而’‘表示它前面的字元可以出現任意次（包含0次）。 在本題中，比對是指字元串的所有字元比對整個模式。例如，字元串”aaa”與模式”a.a”和”ab*ac*a”比對，但是與”aa.a”和”ab*a”均不比對
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
/**
* @author huangeryu
* 實作一個函數用來比對包括'.'和'*'的正規表達式，模式中的字元'.'表示任意一個字元，而'*'表示它前面的字元可以出現任意次（包含0次）
* 思路:利用模式建立不确定性有窮自動機(NFA)，再把NFA轉換為确定性有窮自動機(DFA)
* */
public class Solution
{
private char lookahead;
private char current;
private static int indexIterator=0;
public boolean match(char[] str, char[] pattern)
{
if(pattern!=null && pattern.length!=0)current=pattern[0];
//建構NFA
NFA nfa=new NFA();
for(int i=1;i<=pattern.length;i++)
{
lookahead=(i==pattern.length)?' ':pattern[i];
nfa.construct(lookahead, current);
current=lookahead;
}
//轉換為DFA
DFA dfa=new DFA(nfa);
dfa.construct();
return dfa.matchDfa(str);
}
/**
* @param alphabet 輸入條件
* @param next 滿足輸入條件的下一個節點
* */
class Director
{
private char alphabet;
private Node next;
public Director(char alphabet,Node next)
{
this.alphabet=alphabet;
this.next=next;
}
}
/**
* @param index 節點的名稱
* @param lists 節點對應的出度邊@see Director
* @param isEnd 表示節點是否是接受節點，如果是，為true,否則為false
* */
class Node
{
private final int index;
private ArrayList<Director> lists;
private boolean isEnd;
public Node(int index)
{
this.index=index;
lists=new ArrayList<Director>();
isEnd=false;
}
public int getIndex()
{
return this.index;
}
@Override
public int hashCode()
{
return this.index;
}
@Override
public boolean equals(Object node)
{
if(node instanceof Node)
{
Node temp=(Node)node;
if(temp.index==this.index)return true;
}
return false;
}
}
/**
* @param head 确定有窮自動機的頭節點{@link Node}
* @param nfa 不确定性有窮自動機{@link NFA}
* */
class DFA
{
private Node head;
private NFA nfa;
public DFA(NFA nfa)
{
this.nfa=nfa;
}
/**
* 利用不确定性有窮自動機{@link NFA}構造确定性有窮自動機
* */
public void construct()
{
Deque<Set<Node>> queue=new ArrayDeque<Set<Node>>();
Set<Node> start=new HashSet<Node>();
Map<Set<Node>,Node> map=new HashMap<>();
start.add(nfa.head);
Boolean[] bln={false};
Set<Node> s=nfa.closure_alpha(start, (char)0,bln);
this.head=new Node(indexIterator++);
this.head.isEnd=bln[0];
map.put(s, this.head);
queue.add(s);
while(!queue.isEmpty())
{
Set<Node> t=queue.poll();
Node p=map.get(t);
for(Character c:nfa.set)
{
bln[0]=false;
Set<Node> sn=nfa.closure_alpha(t, c.charValue(),bln);
if(sn.isEmpty())continue;
if(map.containsKey(sn))
{
p.lists.add(new Director(c.charValue(),map.get(sn)));
// System.out.println(p.index+"-->"+map.get(sn).index+" "+c);
}
else
{
Node node=new Node(indexIterator++);
node.isEnd=bln[0];
map.put(sn, node);
p.lists.add(new Director(c.charValue(),node));
// System.out.println(p.index+"-->"+node.index+" "+c+" "+bln[0]);
queue.offer(sn);
}
}
}
}
/**
* @param str 和模式進行比對的字元串
* @return 如果比對成功,傳回true,否則,傳回false
* */
public boolean matchDfa(char[] str)
{
Set<Node>result=new HashSet<Node>();
result.add(head);
Set<Node>temp=new HashSet<Node>();
for(int i=0;i<str.length;i++)
{
char c=str[i];
for(Node np:result)
{
for(Director d:np.lists)
{
if(d.alphabet==c || d.alphabet=='.')temp.add(d.next);
}
}
result.clear();
Set<Node>t=temp;
temp=result;
result=t;
}
for(Node n:result)
{
// System.out.print(n.index+" ");
if(n.isEnd)return true;
}
return false;
}
}
/**
* @param head 不确定性有窮自動機的頭節點{@link Node}
* @param last 總是指向尾部節點,為計算友善而引進
* @param set 節點之間轉移條件的集合{@link Director}
* */
class NFA
{
private Node head;
private Node last;
private HashSet<Character> set;
public NFA()
{
head=new Node(indexIterator++);
last=head;
set=new HashSet<Character>();
}
/**
* 利用兩字元來識别正則法則中的s*模式和s.模式
* @param lookahead 向前看字元
* @param current 目前字元
* */
public void construct(char lookahead,char current)
{
if(current!='*')set.add(current);
if(lookahead==' ')
{
if(current=='*')return;
Node temp=new Node(indexIterator++);
temp.isEnd=true;
last.lists.add(new Director(current,temp));
// System.out.println(last.index+"-->"+temp.index+" "+current);
last=temp;
}
else if(lookahead=='*')
{
Node temp1=new Node(indexIterator++);
Node temp2=new Node(indexIterator++);
Node temp3=new Node(indexIterator++);
last.lists.add(new Director((char)0,temp1));
// System.out.println(last.index+"-->"+temp1.index+" "+0);
last.lists.add(new Director((char)0,temp2));
// System.out.println(last.index+"-->"+temp2.index+" "+0);
temp1.lists.add(new Director(current,temp3));
// System.out.println(temp1.index+"-->"+temp3.index+" "+current);
temp3.lists.add(new Director((char) 0,temp1));
// System.out.println(temp3.index+"-->"+temp1.index+" "+0);
temp3.lists.add(new Director((char)0,temp2));
// System.out.println(temp3.index+"-->"+temp2.index+" "+0);
last=temp2;
}
else if(current!='*')
{
Node temp1=new Node(indexIterator++);
last.lists.add(new Director(current,temp1));
// System.out.println(last.index+"-->"+temp1.index+" "+current);
last=temp1;
}
}
/**
* @param set 輸入集合
* @param alpha 輸入條件{@link NFA}
* @return 輸入集合在輸入條件下轉移的閉包
* @param re 如果傳回的閉包中包含終止節點，則re[0]為true,否則false {@link Node}
* */
public Set<Node> closure_alpha(Set<Node> set,char alpha,Boolean[] re)
{
Set<Node> reSet=new HashSet<Node>();
if(alpha!=0)
{
for(Node n:set)
{
for(Director d:n.lists)
{
if(d.alphabet==alpha)
{
reSet.add(d.next);
if(d.next.isEnd && re!=null)re[0]=true;
}
}
}
}
else
{
reSet.addAll(set);
}
Queue<Node> queue=new ArrayDeque<Node>(reSet);
while(!queue.isEmpty())
{
Node node=queue.poll();
for(Director d:node.lists)
{
if(d.alphabet==0)
{
reSet.add(d.next);
if(d.next.isEnd&& re!=null)re[0]=true;
queue.offer(d.next);
}
}
}
return reSet;
}
}
}
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)