Use char[] or String to present a word?


  • 0
    H

    The following is my accept solution with Trie. It costs 165ms, which beats 97%.

    However if I use String to present the word instead of char[], I receive Time Limit Exceeded. That really confuses me!

    Can String and char[] perform so differently? Any one knows what happen?

        public class WordDictionary {
                private static class Letter {
                    private Letter[] postfixs = new Letter[26];
                    private boolean isEnd;
                }
                
                Letter dummy = new Letter();
    
                public void addWord(String word) {
                    Letter cur = dummy;
                    for (int i = 0; i < word.length(); i++) {
                        int offset = word.charAt(i) - 'a';
                        if (cur.postfixs[offset] == null) {
                            cur.postfixs[offset] = new Letter();
                        }
                        cur = cur.postfixs[offset];
                    }
                    cur.isEnd = true;
                }
    
                public boolean search(String word) {
                    return dfs(word.toCharArray(),0,dummy);
                }
    
                /**
                 *  If I use char[] to present word: 165ms, beats 97%
                 *  If I use String: Time Limit Exceeded
                 *  WHY?
                 */
                public boolean dfs(char[] word, int index, Letter curr) {
                    // base case
                    if (curr == null) { return false; } 
                    if (index == word.length) { return curr.isEnd; }
                    // recursion
                    int offset = word[index] - 'a';
                    if (offset >= 0) { // [a-z]
                        return dfs(word,index+1,curr.postfixs[offset]);
                    } else { // [.]
                        for (Letter l : curr.postfixs) {
                            if (dfs(word,index+1,l)) { return true; }
                        }
                    }
                    return false;
                }
        }
    

Log in to reply
 

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