We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. No Prefix Set
  2. Discussions

No Prefix Set

Sort by

recency

|

13 Discussions

|

  • vadym_usatiuk
     + 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;
        }
    }

  • filip_kujikis
     + 0 comments

    There are at least 3 different orderings of the output that are relevant and fit with the examples.. so this is a really poorly defined problem :(

  • akashmr1096
     + 0 comments

    The testcases are broken in this

    For test case 2

    Correct answer : beeheedjacieefdd Given Answer: ej 

    class TrieNode:
    def __init__(self, data, is_word_end):
        self.data = data
        self.is_word_end = is_word_end
        self.children = {}
        
def add_word_to_trie(word, root):
    if len(word) <= 0:
        root.is_word_end = True
        return
    
    first_char = word[0]
    new_root = root.children.get(first_char, TrieNode(first_char, False))
    root.children[first_char] = new_root
            
    return add_word_to_trie(word[1:], new_root)
    
def has_prefix(word, root):
    if len(word) == 0:
        return False
    
    if root.is_word_end:
        return True
        
    next_root = root.children[word[0]]
    return has_prefix(word[1:], next_root)
    
def noPrefix(words):
    root = TrieNode('*', False)
    words_dict = {}
    for i in range(len(words)):
        add_word_to_trie(words[i], root)
        words_dict[words[i]] = words_dict.get(words[i], 0) + 1
    
    for i in range(len(words)):
        if has_prefix(words[i], root) or words_dict[words[i]] > 1:
            print('BAD SET')
            print(words[i])
            return

    print('GOOD SET')

  • sergmain
     + 1 comment

    Task is broken, don't waste your time on solving this one.

    Why? i.e. for test

    dcjaichjejgheiaie
d
dbeedfdjaghbhgdhcedcj

    you must return d, not dcjaichjejgheiaie even dcjaichjejgheiaie is in first place. test case #1

  • rebel_again1
     + 0 comments
    public class TrieNode {
        char value;
        boolean isLast;
        Map<Character, TrieNode> next = new HashMap<>();
        
        public TrieNode(char value, boolean isLast) {
            this.value = value;
            this.isLast = isLast;
        }
    }
    
    public static void noPrefix(List<String> words) {
        TrieNode root = new Result().new TrieNode('z', false);
        for (String word: words) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode temp = new Result().new TrieNode(c, i == word.length() -1 ? true : false);
                
                if(!node.next.containsKey(c)) {
                    node.next.put(c, temp);
                } else {
                    temp = node.next.get(c);
                    temp.isLast = temp.isLast || i == (word.length() - 1);
                    
                    if(temp.isLast) {
                        System.out.println("BAD SET");
                        System.out.println(word);
                        return;
                    }
                } 
                node = temp;
            }
        }
        System.out.println("GOOD SET");
    }