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

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

让它变得简单 -

Answer 2

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

迭代此列表，对于列表中的每个元素，只需检查下一个元素是否

startsWith()
1. 此元素。如果是，则返回 BAD SET。
2. 如果步骤 2 从未返回 BAD SET，则返回 GOOD SET。
由于排序，复杂度 -> O(n * log n)。

Python 解决方案在这里。

Answer 3

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

Answer 4

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

Answer 5