查找集合中最长的单词

没有 Java 代码。你可以自己弄清楚。

假设我们需要多次这样做，我会这样做：

• 我首先为字典中的每个单词创建“签名”，由26位组成，其中bit[letter]是在单词包含一个（或多个）字母实例的情况下设置的。这些签名可以编码为 Java 。int

• 然后创建一个映射，将签名映射到具有该签名的单词列表。

要使用预先计算的映射执行搜索，请执行以下操作：

• 为要查找其单词的字母集创建签名。

• 然后循环访问映射的键，查找其中 的键。这为您提供了一个简短的“可能”列表，其中不包含任何不在所需字母集中的字母。(key & (~signature) == 0)

• 循环访问短列表，查找每个所需字母数正确的单词，记录最长的命中数。

笔记：

1. 虽然主要搜索大致是字典中的单词数量，但测试非常便宜。O(N)

2. 这种方法的优点是需要相对较小的内存数据结构，该结构（最有可能）具有良好的局部性。这可能有利于更快的搜索。

以下是加快上述搜索步骤的想法。O(N)

从上面的签名映射开始，为所有包含特定对字母的单词创建（预计算）导数映射;即一个用于包含AB的单词，用于AC，BC，...对于YZ。然后，如果你正在寻找包含（比如）P和Q的单词，你可以扫描PQ导数映射。这将减少大致的步伐...代价是额外地图的更多内存。O(N)26^2

这可以扩展到3个或更多字母，但缺点是内存使用量的爆炸式增长。

另一个潜在的调整是（以某种方式）将初始字母对的选择偏向于不经常出现的字母/对。但这会增加前期开销，这可能大于您从搜索较短列表中获得的（平均）节省。

首先，好问题。面试官想看看你如何解决这个问题。在这类问题中，您需要分析问题并仔细选择数据结构。

在这种情况下，我脑海中浮现出两个数据结构：和。 不是很合适，因为你没有一个完整的键，你想查找（你可以使用基于地图的倒排索引，但你说你已经找到了这些解决方案）。你只有零件 - 这是最适合的地方。HashMapsTriesHashMapsTrie

因此，尝试的想法是，您可以在遍历树时忽略字典中没有的字符分支。

在你的例子中，树看起来像这样（我省略了非分支路径的分支）：

*
   a
     bacus
   d 
     deltoid
   g
     a
       gaff
     i
       giraffe
   m 
     microphone
   r 
     reef
   q 
     qar

因此，在这个trie的每个级别，我们查看当前节点的子节点，并检查子节点的字符是否在我们的字典中。

如果是：我们深入到那棵树中，从我们的字典中删除孩子的性格

这一直持续到你碰到一片叶子（不再有孩子了），在这里你知道这个词包含了这本字典中的所有字符。这是一个可能的候选者。现在我们想回到树中，直到找到另一个可以比较的匹配项。如果最新找到的匹配项较小，请丢弃它，如果时间更长，则这是我们现在可能的最佳匹配候选项。

总有一天，回避会结束，你最终会得到所需的输出。

请注意，如果有一个最长的单词，这有效，否则您必须返回候选人列表（这是面试的未知部分，您需要询问面试官希望看到什么作为解决方案）。

所以你需要Java代码，这里是一个简单和最长的单词版本：Trie

public class LongestWord {

  class TrieNode {
    char value;
    List<TrieNode> children = new ArrayList<>();
    String word;

    public TrieNode() {
    }

    public TrieNode(char val) {
      this.value = val;
    }

    public void add(char[] array) {
      add(array, 0);
    }

    public void add(char[] array, int offset) {
      for (TrieNode child : children) {
        if (child.value == array[offset]) {
          child.add(array, offset + 1);
          return;
        }
      }
      TrieNode trieNode = new TrieNode(array[offset]);
      children.add(trieNode);
      if (offset < array.length - 1) {
        trieNode.add(array, offset + 1);
      } else {
        trieNode.word = new String(array);
      }
    }    
  }

  private TrieNode root = new TrieNode();

  public LongestWord() {
    List<String> asList = Arrays.asList("abacus", "deltoid", "gaff", "giraffe",
        "microphone", "reef", "qar");
    for (String word : asList) {
      root.add(word.toCharArray());
    }
  }

  public String search(char[] cs) {
    return visit(root, cs);
  }

  public String visit(TrieNode n, char[] allowedCharacters) {
    String bestMatch = null;
    if (n.children.isEmpty()) {
      // base case, leaf of the trie, use as a candidate
      bestMatch = n.word;
    }

    for (TrieNode child : n.children) {
      if (contains(allowedCharacters, child.value)) {
        // remove this child's value and descent into the trie
        String result = visit(child, remove(allowedCharacters, child.value));
        // if the result wasn't null, check length and set
        if (bestMatch == null || result != null
            && bestMatch.length() < result.length()) {
          bestMatch = result;
        }
      }
    }
    // always return the best known match thus far
    return bestMatch;
  }

  private char[] remove(char[] allowedCharacters, char value) {
    char[] newDict = new char[allowedCharacters.length - 1];
    int index = 0;
    for (char x : allowedCharacters) {
      if (x != value) {
        newDict[index++] = x;
      } else {
        // we removed the first hit, now copy the rest
        break;
      }
    }
    System.arraycopy(allowedCharacters, index + 1, newDict, index,
        allowedCharacters.length - (index + 1));

    return newDict;
  }

  private boolean contains(char[] allowedCharacters, char value) {
    for (char x : allowedCharacters) {
      if (value == x) {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    LongestWord lw = new LongestWord();
    String longestWord = lw.search(new char[] { 'a', 'e', 'f', 'f', 'g', 'i',
        'r', 'q' });
    // yields giraffe
    System.out.println(longestWord);
  }

}

我也只能建议你阅读《破解编码面试：150个编程问题和解决方案》一书，它指导你完成决策和构建那些专门针对面试问题的算法。