使用用户输入的字符串，找到可以组成的最长单词。

Question

基本上，我想创建一个程序，模拟 Channel 4 的“Countdown”游戏。实际上，用户必须输入 9 个字母，程序将搜索字典中可以由这些字母组成的最大单词。我认为树结构比哈希表更好。我已经有一个包含字典中单词的文件，并将使用文件 io。

这是我的文件 io 类：

public static void main(String[] args){
     FileIO reader = new FileIO();
     String[] contents = reader.load("dictionary.txt");
}

这是我在倒计时类中已经完成的部分：

public static void main(String[] args) throws IOException{
     Scanner scan = new Scanner(System.in);
     letters = scan.NextLine();
}

我在这里完全迷失了方向。我知道这只是开始，但我并不想寻找答案。我只是想得到一点帮助，也许能给我指个方向。我对Java很新，在一本面试书中发现了这个问题，所以我想尝试一下。

提前感谢您的帮助。

- user3376340

---

我认为你可以使用后缀树和字符串搜索来实现这个功能。 - Elliott Frisch

请澄清一下 - 如果在您的九个字母中只出现一次，那么在单词中重复相同的字母是否合法？ - Dawood ibn Kareem

你选择了一个相当困难的问题来开始，特别是如果你谈论的是一个真正的词典（即数十万个单词）。这通常使用一种叫做有向无环字图（DAWG）的东西来完成，这是一个相当高级的主题。 - Jim Mischel

Answer 1

首先的方法可以是使用包含单词列表中所有字母的树。

如果一个节点是一个单词的结尾，则标记为一个单词结尾节点。

在上面的图片中，最长的单词是banana。但是还有其他单词，比如ball、ban或banal。

因此，一个节点必须具备以下特点：

1. 一个字符
2. 如果它是一个单词的结尾
3. 一个子节点列表（最多26个）

插入算法非常简单：在每一步中，我们“剪切”单词的第一个字符，直到单词没有更多字符为止。

public class TreeNode {

    public char c;
    private boolean isEndOfWord = false;
    private TreeNode[] children = new TreeNode[26];

    public TreeNode(char c) {
        this.c = c;
    }

    public void put(String s) {
        if (s.isEmpty())
        {
            this.isEndOfWord = true;
            return;
        }
        char first = s.charAt(0);
        int pos = position(first);
        if (this.children[pos] == null)
            this.children[pos] = new TreeNode(first);

        this.children[pos].put(s.substring(1));
    }

    public String search(char[] letters) {
        String word = "";
        String w = "";

        for (int i = 0; i < letters.length; i++)
        {
            TreeNode child = children[position(letters[i])];
            if (child != null)
                w = child.search(letters);
               //this is not efficient. It should be optimized.
            if (w.contains("%")
                    && w.substring(0, w.lastIndexOf("%")).length() > word
                            .length())
                word = w;
        }
            // if a node its end-of-word we add the special char '%'
        return c + (this.isEndOfWord ? "%" : "") + word;
    }
    //if 'a' returns 0, if 'b' returns 1...etc
    public static int position(char c) {
        return ((byte) c) - 97;
    }


}

例子：

public static void main(String[] args) {
    //root
    TreeNode t = new TreeNode('R');
    //for skipping words with "'" in the wordlist
    Pattern p = Pattern.compile(".*\\W+.*");
    int nw = 0;
    try (BufferedReader br = new BufferedReader(new FileReader(
            "files/wordsEn.txt")))
    {
        for (String line; (line = br.readLine()) != null;)
        {
            if (p.matcher(line).find())
                continue;
            t.put(line);
            nw++;
        }
        // line is not visible here.
        br.close();
        System.out.println("number of words : " + nw);
        String res = null;
        // substring (1) because of the root
        res = t.search("vuetsrcanoli".toCharArray()).substring(1);
        System.out.println(res.replace("%", ""));
    }

    catch (Exception e)
    {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

}

输出：

number of words : 109563
counterrevolutionaries

---

注：

• 单词列表取自此处
• 阅读部分基于另一个SO问题：如何使用Java逐行读取大型文本文件？

- rpax

Answer 2

欢迎来到Java的世界 :)

我看到你有两个主要方法，实际上你并不需要那么多。在大多数情况下，你的程序只需要一个入口点，然后它会处理所有逻辑和用户输入等。

你考虑了一棵树形结构，这很好，但可能有更好的存储方式。试试这个：http://en.wikipedia.org/wiki/Trie

你的程序需要逐行读取文件中的所有单词，并在此过程中构建你的数据结构——树。完成后，你可以要求用户输入，然后搜索树。

由于你明确要求不提供答案，所以我不会在这里放置代码，但如果你对某些内容不清楚，请随时问我。

- maczikasz

---

我也建议采用 Trie 数据结构，每个节点保存字典单词中的一个字符。这样你的程序就可以根据每一步未使用的字母来遍历节点。 - Martin

一种特定类型的trie，即有向无环字图（Directed Acyclic Word Graph），是解决这类问题的著名数据结构。 - Jim Mischel

Answer 3

英语中只有大约800,000个单词，因此一种高效的解决方案是将这些800,000个单词存储为800,000个数组，每个数组包含26个1字节整数，用于计算单词中每个字母出现的次数。对于一个输入的9个字符，您可以将其转换为类似的26个整数计数格式进行查询，然后如果查询向量在分量上大于或等于单词向量，则可以从查询字母中形成单词。通过这种方式，您可以轻松地处理大约100个查询每秒。

- user2566092

---

这听起来并不是非常高效。除非我漏掉了什么。似乎搜索至少是O(n)，而且对于每个单词，您都必须检查很多字母组合。您能解释一下搜索如何工作吗？ - Jim Mischel

@JimMischel 对于每个单词，您无需检查一堆字母组合，只需将该单词的字母计数向量与查询字母的字母计数向量进行比较。如果查询字母提供的字母计数大于或等于单词的字母计数，则该单词可以由查询中的字母组成。每次查询的总复杂度为O（nA），其中n为单词数，A为字母表大小。应该能够每秒执行一百个以上的查询。 - user2566092

一个O(nA)搜索非常昂贵。有更有效的方法来完成这个任务。 - Jim Mischel

@JimMischel n = 800k，A = 26，而且隐藏的常数非常低，这将使每秒数百个查询成为可能。OP询问的是实际的英语语言，而不是具有巨大n和A的假想语言，这将使每秒数百个查询成为可能。如果OP希望更快，应该说明；否则，尽管简单，但这似乎是一个完美的解决方案。实际上，当简单足够好时，我认为简单是首选。 - user2566092

Answer 4

我会编写一个程序，从所有的两个字母单词开始，然后是三个字母的单词，四个字母的单词等等。

当你处理两个字母的单词时，你需要一种方法来选择第一个字母，然后从剩下的字母中选择第二个字母。你可能需要使用递归来完成这部分。最后，你将检查它是否在字典中。尝试以一种方式编写它，使得你可以重复使用相同的代码来处理三个字母的单词。

- Dawood ibn Kareem

Answer 5

我相信，在你的情况下，正则表达式 的威力会派上用场：

1）创建一个带有符号类的正则表达式字符串，例如：/^[abcdefghi]*$/，将你的字母替换成“abcdefghi”中的字母。

2）使用该正则表达式作为过滤器，从文本文件中获取一个字符串数组。

3）按长度排序。最长的单词就是你需要的！

查看正则表达式参考以获取更多信息。

更新：这里有一个很好的Java正则表达式教程。

- dnl-blkv

---

/^[abcdefghi]*$/将匹配所有内容，甚至包含不含这些字母的单词。你需要用+替换掉*。即便如此，你的方法仍需查看每个单词。如果你想要每秒进行数百次查找，那么效率并不高。 - Jim Mischel