0

我正在做一个小项目（在 Java 中），而 uni 只是为了测试自己而我遇到了一个绊脚石。

我正在尝试编写一个程序，该程序将从文本版本的字典中读取，将其存储在 ds（数据结构）中，然后向用户询问随机字符串（最好是无意义的字符串，但只有字母和 - ，没有数字或其他标点符号 - 我对其他任何东西都不感兴趣），找出输入字符串的所有字谜，将其与字典 ds 进行比较，并返回字典中所有可能的字谜的列表。

好的，对于第 1 步和第 2 步（从字典中读取），当我阅读其中的所有内容时，我将其存储在 Map 中，其中键是字母表中的字母，值是 ArrayLists，存储所有以该字母开头的单词.

我一直在寻找所有的字谜，我想出了如何递归地（自豪地）计算可能排列的数量，我不确定如何实际进行重新排列。

将其分解为 char 并以这种方式使用它，还是将其拆分并保留为字符串元素更好？我已经在不同的网站上在线看到了示例代码，但我不想看到代码，我想知道为此开发解决方案背后的方法/想法，因为我有点卡住了如何开始:(

我的意思是，我想我知道一旦我生成了所有排列，我将如何与字典 ds 进行比较。

任何建议都会有所帮助，但如果可以的话，不要编码，只是想法。

PS如果你想看到我的代码到目前为止（无论出于何种原因），我会发布我所拥有的。

4

3 回答 3

4 
public String str = "overflow";
public ArrayList<String> possibilities = new ArrayList<String>();
public void main(String[] args)
{
    permu(new boolean[str.length()],"");
}
public void permu(boolean[] used, String cur)
{
    if (cur.length()==str.length())
    {
        possibilities.add(cur);
        return;
    }
    for (int a = 0; a < str.length(); a++)
    {
        if (!used[a])
        {
            used[a]=true;
            cur+=str.charAt(a);
            permu(used,cur);
            used[a] = false;
            cur = cur.substring(0,cur.length()-1);
        }
    }
}

简单，运行时间非常糟糕，但它会完成工作。

编辑：更高级的版本是一个叫做字典树的东西。基本上它是一棵树，其中每个节点有 26 个节点，每个节点对应字母表中的每个字母。每个节点也有一个布尔值来判断它是否是一个单词的结尾。有了这个，您可以轻松地将单词插入字典并轻松检查您是否在创建单词的正确路径上。

如果您愿意，我将粘贴代码

于 2011-06-08T16:00:09.537 回答
3

在这种情况下，计算排列似乎真的是个坏主意。例如，“溢出”这个词有 40320 个排列。

找出一个词是否是另一个词的排列的更好方法是计算每个字母出现的次数（它将是一个 26 元组）并将这些元组相互比较。

于 2011-06-08T15:47:55.973 回答
2

如果您举例说明问题可能会有所帮助。据我了解，您是说如果用户输入“islent”，程序将回复“listen”、“silent”和“enlist”。

我认为最简单的解决方案是获取字典中的每个单词并将其与输入的单词一起存储，并且将单词与字母重新排列成字母顺序的单词一起存储。我们称其为“规范值”。规范值的索引。然后将输入转换为规范值，并直接搜索匹配项。

继续上面的例子，当我们构建字典并看到单词“listen”时，我们会将其翻译为“eilnst”并存储“eilnst -> listen”。我们还会存储“eilnst -> silent”和“eilnst -> enlist”。然后我们获取输入字符串，将其转换为“eilnst”，进行搜索并立即找到三个匹配项。

于 2011-06-08T15:51:58.387 回答