Another solution of using HashTable to store all prefixes (but TLE)


  • 0

    This is my first initial solution but it get TLE, i think it is interesting to analyze this and compare with Trie ones. This solution seems to find hashValue of common prefix many many times, which takes time; and also the String concatenation takes time as well. While in Trie, common prefix is only traversed once. And in space complexity, HashTable stores every possible prefixes, which is significant larger than Trie ones.

    Are there any improvements to the below code to make it faster ??

    public class WordDictionary {
        
        Set<String> wordCache = new HashSet<String>();
        Set<String> prefixCache = new HashSet<String>();
    
        public void addWord(String word) {
            StringBuilder sb = new StringBuilder();
            for(char c : word.toCharArray())
                prefixCache.add(sb.append(c).toString());
            wordCache.add(word);
        }
        
        private boolean searchHelper(String head, String tail) {
            int idxOfDot = tail.indexOf('.');
            if(idxOfDot<0) {
                return wordCache.contains(head+tail);
            } else {
                String newTail = tail.substring(idxOfDot);
                for(int i=0; i<26; i++) {
                    String newHead = head + tail.substring(0,idxOfDot) + (char)('a'+i);
                    if(prefixCache.contains(newHead) && searchHelper(newHead, newTail))
                        return true;
                }
                return false;
            }
        }
    
        public boolean search(String word) {
            return searchHelper("",word);
        }
    }

Log in to reply
 

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