No Prefix Set

  • + 0 comments

    Java O(n*L)

    class TrieNode {
            TrieNode[] children = new TrieNode[26];
            boolean isEndOfWord = false;
        }
    
         class Result {
            public static void noPrefix(List<String> words) {
                TrieNode root = new TrieNode();
                for (String word : words) {
                    if (!insert(root, word)) {
                        System.out.println("BAD SET");
                        System.out.println(word);
                        return;
                    }
                }
                System.out.println("GOOD SET");
            }
    
            private static boolean insert(TrieNode root, String word) {
                TrieNode current = root;
                for (int i = 0; i < word.length(); i++) {
                    int index = word.charAt(i) - 'a';
                    if (current.children[index] == null) {
                        current.children[index] = new TrieNode();
                    }
                    current = current.children[index];
                    if (current.isEndOfWord) {
                        return false;
                    }
                }
                current.isEndOfWord = true;
                for (TrieNode child : current.children) {
                    if (child != null) {
                        return false;
                    }
                }
                return true;
            }
        }