Simple Java Solution using Trie

  • 2
    	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:
    	search("pad") -> false
    	search("bad") -> true
    	search(".ad") -> true
    	search("b..") -> true
    	You may assume that all words are consist of lowercase letters a-z.
    class TrieNode{
        String value;
        HashMap<Character, TrieNode> children = null;
        Boolean flag;
        public TrieNode(){
            value = null;
            children = new HashMap<>();
            flag = Boolean.FALSE;
        public TrieNode(String value){
            this.value = value;
            children = new HashMap<>();
            flag = Boolean.FALSE;
        public void add(Character c){
            String val = "";
            if(this.value == null){ //root node
                val = String.valueOf(c);
                val = this.value + String.valueOf(c);
            this.children.put(c, new TrieNode(val));
    class Trie{
        TrieNode root = null;
        public Trie(){
            root = new TrieNode();
        public void addWord(String word){
            TrieNode node = root;
            for(Character c: word.toCharArray()){
                node = node.children.get(c);
            node.flag = true;
        public TrieNode getRoot(){
            return root;
    public class WordDictionary {
        Trie trie = new Trie();
        // Adds a word into the data structure.
        public void addWord(String word) {
        public boolean searchPattern(TrieNode node, String pattern, int counter){
            if(node == null) return false;    
            if(counter == pattern.length()) return node.flag;
            Character c = pattern.charAt(counter);
            if(c == '.'){
                for(Character ch: node.children.keySet()){
                    if(searchPattern(node.children.get(ch), pattern, counter+1)) return true;
            }else if(c != '.' && node.children.containsKey(c)) {
                return searchPattern(node.children.get(c), pattern, counter+1);
            return false;
        // 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 searchPattern(trie.getRoot(), word, 0);
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");

Log in to reply

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