Java Trie Solution, beat 98%


  • 0
    4
    public class Solution {
        TrieNode root = new TrieNode();
        public String replaceWords(List<String> dict, String sentence) {
            for (String d : dict) {
                insert(d);
            }
            
            String[] words = sentence.split(" ");
            StringBuilder sb = new StringBuilder();
            for (String word : words) {
                sb.append(searchRoot(word));
                sb.append(" ");
            }
            
            return sb.deleteCharAt(sb.length() - 1).toString();
        }
        
        public void insert(String word) {
            TrieNode cur = root;
            TrieNode[] children = cur.children;
            for (int i = 0; i < word.length(); i++) {
                if (cur.hasWord)
                    break;
                char c = word.charAt(i);
                if (children[c - 'a'] == null)
                    children[c - 'a'] = new TrieNode();
                cur = children[c - 'a'];
                children = cur.children;
            }
            cur.hasWord = true;
        }
        
        public String searchRoot(String word) {
            StringBuilder sb = new StringBuilder();
            TrieNode cur = root;
            TrieNode[] children = cur.children;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                cur = children[c - 'a'];
                if (cur == null)
                    return word;
                children = cur.children;
                sb.append(c);
                if (cur.hasWord)
                    break;
            }
            return sb.toString();
        }
    }
    
    class TrieNode {
        TrieNode[] children;
        boolean hasWord;
        public TrieNode() {
            children = new TrieNode[26];
        }
        
    }
    

Log in to reply
 

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