Trie Tree concise Java solution, easy to understand


  • 2
    S
    public class Solution {
        TrieNode root = new TrieNode();
        
        public String replaceWords(List<String> dict, String sentence) {
            StringBuilder sb = new StringBuilder();
            String[] words = sentence.split(" ");
            for (String word : dict) {
                build(word);
            }
            for (String word : words) {
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                sb.append(next(word));
            }
            return sb.toString();
        }
        
        public void build(String word) {
            TrieNode curRoot = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (curRoot.children[c - 'a'] == null) {
                    curRoot.children[c - 'a'] = new TrieNode();
                }
                curRoot = curRoot.children[c - 'a'];
            }
            curRoot.isTail = true;
        }
        
        public String next(String word) {
            TrieNode curRoot = root;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (curRoot.children[c - 'a'] == null) {
                    break;
                }
                sb.append(c);
                curRoot = curRoot.children[c - 'a'];
                if (curRoot.isTail) return sb.toString();
            }
            return word;
        }
    }
    
    class TrieNode {
        TrieNode[] children;
        boolean isTail = false;
        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.