HackerRank - No Prefix Set 未通过所有测试用例

Question

我试图解决 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
啊啊啊
啊啊啊

输出：
错误设置
呜呜呜

Answer 1

让它变得简单 -

根据给定的集合创建一个排序列表。
遍历这个列表，对于列表中的每个元素只检查下一个元素是否startsWith()这个元素。如果是 return BAD SET.
Return 如果第 2 步从不 returns 错误设置。

复杂度 -> O(n * log n) 由于排序。

Answer 2

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

您还必须检查当前单词是否是 Trie 中已有单词的前缀。

Answer 3

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");
}

HackerRank - No Prefix Set 未通过所有测试用例

HackerRank - No Prefix Set not passing all the test cases

java

trie

data-structures