Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters?a-z?or?.. A?.?means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

public class WordDictionary {

	private Trie trie = new Trie();
    // Adds a word into the data structure.
    public void addWord(String word) {
    	trie.insert(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character ‘.‘ to represent any one letter.
    public boolean search(String word) {
    	return trie.search(word);
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
class Trie {
	private TrieNode root = new TrieNode();

	public void insert(String word) {
		root.insert(word.toCharArray(), 0);
	}

	public boolean search(String word) {
		return root.search(word.toCharArray(), 0);
	}
}
class TrieNode {
	private TrieNode[] nodes;
	private boolean end;
	public TrieNode() {
		int size = 26;
		nodes = new TrieNode[size];
		end = false;
	}
	public void insert(char[] chars, int start) {
		if (start == chars.length) {
			end = true;
			return;
		}
		int idx = getIndex(chars[start]);
		if (idx == -1) {
			for (int i = 0; i < nodes.length; i++) {
				insert(i, chars, start);
			}
		} else {
			insert(idx, chars, start);
		}
	}
	private void insert(int i, char[] chars, int start) {
		// TODO Auto-generated method stub
		TrieNode node = nodes[i];
		if (node != null) {
			node.insert(chars, start+1);
		} else {
			node = new TrieNode();
			nodes[i] = node;
			node.insert(chars, start+1);
		}
	}
	private int getIndex(char c) {
		// TODO Auto-generated method stub
		if (c == ‘.‘) {
			return -1;
		}
		return c - ‘a‘;
	}
	public boolean search(char[] chars, int start) {
		if (start == chars.length) {
			return end;
		}
		char c = chars[start];
		int idx = getIndex(c);
		if (idx == -1) {
			for (int i = 0; i < nodes.length; i++) {
				boolean flag = search(i, chars, start);
				if (flag) {
					return true;
				}
			}
			return false;
		} else {
			return search(idx, chars, start);
		}
	}

	private boolean search(int i, char[] chars, int start) {
		// TODO Auto-generated method stub
		TrieNode node = nodes[i];
		if (node == null) {
			return false;
		}
		return node.search(chars, start + 1);
	}
}

?

Add and Search Word - Data structure design

原文：http://hcx2013.iteye.com/blog/2252474