Longest Common Prefix Solution with Trie Tree


  • 1
    class TrieNode {
        Map<Character, TrieNode> children;
        boolean isWord;
    
        public TrieNode() {
            children = new HashMap<>();
            isWord = false;
        }
    }
    class Trie {
        public TrieNode root;
    
        public Trie () {
            root = new TrieNode();
        }
    
        public void insert (String str) {
            TrieNode cur = root;
            for (int i = 0; i < str.length(); i++) {
                Map<Character, TrieNode> children = cur.children;
                //get the next TrieNode
                char ch = str.charAt(i);
                TrieNode next = children.get(ch);
                if (next == null) {
                    children.put(ch, new TrieNode());
                }
    
                cur = children.get(ch);
            }
            cur.isWord = true;
        }
    }
    
    public class Solution {
        public String longestCommonPrefix(String[] strs) {
            //corner case
    
            Trie trie = new Trie();
            for (String str : strs) {
                if (str.length() == 0) {
                    return new String();
                }
                trie.insert(str);
            }
    
            //check branck
            StringBuilder sb = new StringBuilder();
            TrieNode cur = trie.root;
    
            while (cur.children.size() == 1 && !cur.isWord) {
                Iterator iter = cur.children.keySet().iterator();
                while (iter.hasNext()) {
                    Character ch = (Character)iter.next();
                    sb.append(ch);
                    cur = cur.children.get(ch);
                }
            }
    
            return String.valueOf(sb);
        }
    }
    

Log in to reply
 

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