问题标签 [anagram]

我最近被要求设计一种算法来检查两个字符串是否是彼此的字谜。我的目标是最小化空间和时间复杂度，所以我想出了这个算法：

1. 创建一个包含 26 个元素的数组，每个元素都初始化为零。
2. 遍历第一个字符串并为每个字符递增对应于该字符的数组元素。
3. 遍历第二个字符串，并为每个字符递减对应于该字符的数组元素。
4. 扫描阵列。如果所有元素都为 0，则这两个字符串是字谜。

但是，这个算法的时间复杂度是 O(n)，我想不出一个复杂度更低的算法。有人知道吗？

我用这个（非常低效的方法）解决了这个问题：

大约需要 10 分钟才能找到具有最多字典有效字谜的五个字母单词。我想在没有字母限制的单词上运行它，但这会花费大量时间。反正有没有优化这个？

如何在 javascript 中创建一个单词的所有可能字谜的列表？如果这个问题已经被问过，请指导我回答？

谢谢你

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

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

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

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

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

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

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

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

我知道以前有人问过这个变体，但是我无法理解以前的任何实现，因为它们中的大多数都涉及使用集合和 issubset 方法。

这是我想要做的：我在字典中有一组单词和一个可能的字母列表。我想通过重新排列列表中的字母来查找是否可以形成集合的成员。这是我当前的实现：

这种实现的一个明显问题是会发现一些单词在“字母”中使用了多个字母。例如，单词“cardboard”显示为有效单词，尽管字母列表中只有一个“a”和“r”副本。如何在列表中使用“issubset”方法？

我有一个单词列表和一个包含许多字谜的文件。这些字谜是在单词列表中找到的单词。我需要开发一种算法来查找匹配的单词并将它们生成在输出文件中。到目前为止，我开发的代码仅适用于前两个单词。此外，我无法让代码与其中任何地方包含数字的字符串一起玩得很好。请告诉我如何修复代码。

我正在制作一个移动应用程序来查找字谜和部分匹配。移动很重要，因为没有大量的计算能力，而效率是关键。

该算法采用任意数量的字母，包括重复字母，并找到由其字母组成的最长单词，每个字母只使用一次。我也有兴趣快速找到最佳结果，只要满足 N，我并不真正关心底部（较短的）。例如：

我做了一些谷歌搜索并找到了一些算法，我想出了一个我认为会很有效的算法，但没有我想要的那么高效。

我有一个预先制作的查找字典，它将排序的键映射到生成该键的真实单词。

我根据键的长度将每个字典进一步拆分为不同的字典。所以 5 个字母长的键在一个字典中，6 个字母的键在另一个字典中。这些字典中的每一个都位于一个数组中，其中索引是在字典中找到的键的长度。

我的算法从输入单词“ lappe”开始，然后对其进行排序：

现在，对于每本最多包含 5 个字母的字典，我进行比较以将其提取出来。这是伪代码：

该词典中只有大约 170,000 个单词，但对于 12 个字母的输入，搜索最多需要 20 秒。我的match方法从密钥中生成了一个正则表达式：

这样，例如，一个 4 个字母的键，如acst(acts)，将匹配ackst(stack)，因为：

我已经看到其他应用程序在更短的时间内做同样的事情，我想知道我的方法是垃圾还是只需要一些调整。

我怎样才能获得最大的计算效率来从一个单词中生成前 N 个字谜，按最大长度排序？

我正在尝试使用一种非常基本的程序方法来创建一个字谜求解器。我发现我可能应该使用课程来完成这项工作，但现在为时已晚，我的作业即将到期。任何关于如何解决这个问题的建议都会很棒！

基本上，这就是算法应该做的：

1. 获取字典中的所有单词；将它们存放在容器中
2. 从用户那里得到一句话；适当时退出
3. 获取用户输入的单词的所有排列
4. 从排列中去除用户输入的单词
5. 删除排列集合中不在我在第 1 部分中收集的字典中的所有单词

现在对于最后一步，我必须确保不显示重复的字谜（即包含相同字母的字谜，例如“循环”）。我似乎无法让这个检查工作，这在下面的 TODO 注释块下有说明。

任何建议都会很棒！

每次我尝试运行程序时，都会弹出一个“Anagram”并且我无法运行我的程序。如何让它消失？谢谢

在 O(nlogn) 时间对两个字符串进行排序后，您可以找到 2 个字符串是否是字谜，但是是否有可能在 o(n) 时间和 O(1) 空间中找到它。