HackerRank - 无前缀集未通过所有测试用例

问题描述 投票:0回答:5

我试图解决 HackerRank 上的 No Prefix Set 问题。我的解决方案仅通过了一半的测试用例。我没有得到我在这里缺少的东西。

问题陈述:给定N个字符串。每个字符串仅包含来自

a−j
的小写字母(包含两者)。 N 个字符串的集合被称为“GOOD SET”,如果没有字符串是另一个字符串的前缀,则称为“BAD SET”。 例如:

aab

abcde

aabcd
BAD SET
,因为
aab
aabcd的前缀。

这是我实现的逻辑。

class Trie { Trie next[] = new Trie[10]; boolean end[] = new boolean[10]; } private static void goodOrBad(String[] array, Trie start) { for (String string : array) { Trie current = start; Trie previous = start; int index = 0; char strArray[] = string.toCharArray(); for (char c : strArray) { index = c-'a'; if (current.end[index]) { System.out.println("BAD SET"); System.out.println(string); return; } if (current.next[index] == null) { Trie newTrie = new Trie(); current.next[index] = newTrie; previous = current; current = newTrie; } else { previous = current; current = current.next[index]; } } previous.end[index] = true; } System.out.println("GOOD SET"); }

输入:

第一行包含 N,即集合中字符串的数量。

接下来是 N 行,其中第 i 行包含第 i 个字符串。
输出:

如果设置有效,则输出

GOOD SET 否则,输出
BAD SET,后跟条件失败的
first string

示例:

4

aab aac 啊啊啊啊
啊啊啊


输出:

糟糕的设置

啊啊啊啊

问题是您只是检查当前单词是否包含前一个单词作为前缀。

java data-structures trie
5个回答
5
投票

让它变得简单 -


1
投票
从给定的集合中创建一个排序列表。

迭代此列表,对于列表中的每个元素,只需检查下一个元素是否
    startsWith()
  1. 此元素。如果是,则返回 BAD SET。
  2. 如果步骤 2 从未返回 BAD SET,则返回 GOOD SET。
    
    
    
  3. 由于排序,复杂度 -> O(n * log n)。

Python 解决方案在这里。


0
投票

class Tree: def __init__(self, words): self.words = words self.root = Node(None) self.checkForPrefix() def checkForPrefix(self): for word in words: answer = self.insert(word) if answer is not None: print("BAD SET") print(answer) return print("GOOD SET") def insert(self, word): current = self.root for i in range(len(word)): c = word[i] if current.branches[self.indexOf(c)] != None and i == len(word) - 1: return word if current.branches[self.indexOf(c)] == None: current.branches[self.indexOf(c)] = Node(c) if current.branches[self.indexOf(c)].isComplete: return word if i == len(word) - 1: current.branches[self.indexOf(c)].isComplete = True current = current.branches[self.indexOf(c)] return None def indexOf(self, c): return ord(c) - 97 class Node: def __init__(self, value): self.value = value self.isComplete = False self.branches = [None] * (ord("j") - ord("a") + 1) def noPrefix(words): # Write your code here root = Tree(words)

Trie 的想法很好,只是你需要为这个特定问题定义自定义 trie

0
投票

class Result { public static void noPrefix(final List<String> words) { final String prefix = anyElemAsPrefix(words).orElse(null); if (prefix != null) { System.out.println("BAD SET"); System.out.println(prefix); } else { System.out.println("GOOD SET"); } } private static Optional<String> anyElemAsPrefix(final List<String> words) { final PrefixCheckTrie prefixCheckTrie = new PrefixCheckTrie(); for (final String word : words) { if (prefixCheckTrie.hasAnyKeyWithPrefix(word)) { return Optional.of(word); } prefixCheckTrie.add(word); } return Optional.empty(); } private static final class PrefixCheckTrie { private static final int r = 256; private Node root; public boolean hasAnyKeyWithPrefix(String prefix) { return matchedSymbols(root, prefix, 0, new StringBuilder()).length() > 0; } private StringBuilder matchedSymbols(final Node x, final String key, final int d, final StringBuilder matchedCharacters) { if (x == null) return matchedCharacters; if (d == key.length()) return matchedCharacters; char c = key.charAt(d); if (x.next[c] == null) { return x.isWord ? matchedCharacters : new StringBuilder(); } return matchedSymbols(x.next[c], key, d + 1, matchedCharacters.append(c)); } public void add(final String key) { if (key == null) { throw new IllegalArgumentException("argument to add() is null"); } root = add(root, key, 0); } private Node add(Node x, String key, int d) { if (x == null) x = new Node(r); if (d == key.length()) { x.isWord = true; } else { char c = key.charAt(d); x.next[c] = add(x.next[c], key, d + 1); } return x; } private static class Node { private final Node[] next; private boolean isWord; public Node(final int r) { this.next = new Node[r]; } } } }

public static void noPrefix(List<String> words) {
// here is the solution which worked for me in hackerrank. let me know if any 
// better suggestion
   HashSet<String> hashSet=new LinkedHashSet<String>();
    for (String curr : words) {
        if(hashSet.size()>1){
        for (String value : hashSet) {
          if(!curr.equalsIgnoreCase(value) 
          &&  curr.startsWith(value)){
              System.out.println("BAD SET");
              System.out.println(curr);
            return;
          }
        }
        }
        hashSet.add(curr);
    }
    System.out.println("GOOD SET");
}

-1
投票
© www.soinside.com 2019 - 2024. All rights reserved.