java trie 88%


  • 0
    C

    public class Solution {
    TrieNode root = new TrieNode();

    public String replaceWords(List<String> dict, String sentence) {
        if(dict == null || sentence == null) return sentence;
        // set up Tire
        genTrie(dict, root);
        // replace words
        String[] words = sentence.trim().split(" ");
        for(int i = 0; i < words.length; i++) {
            String str = isReplacable(words[i]);
            if(str != null)
                words[i] = str;
        }
        StringBuilder sb = new StringBuilder();
        for(String s : words) {
            sb.append(s).append(" ");
        }
        return sb.substring(0, sb.length()-1);
    }
    
    private void genTrie(List<String> dict, TrieNode root) {
        if(dict == null) return;
        for(String str : dict) {
            TrieNode node = root;
            char[] cs = str.toCharArray();
            for(char c : cs) {
                if(node.children[c - 'a'] == null)
                    node.children[c - 'a'] = new TrieNode();
                node = node.children[c - 'a'];
            }
            node.word = str;
            node.isEnd = true;
        }
    }
    
    private String isReplacable(String orig) {
        TrieNode node = root;
        for(char c : orig.toCharArray()) {
            if(node.children[c - 'a'] != null) {
                if(node.children[c - 'a'].isEnd) 
                    return node.children[c - 'a'].word;
                else
                    node = node.children[c - 'a'];
            } else {
                return null;
            }
        }
        return null;
    }
    

    }
    class TrieNode {
    boolean isEnd = false;
    String word = "";
    TrieNode[] children = new TrieNode[26];
    public TrieNode () {}
    }


Log in to reply
 

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