- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试解决古老的字谜问题。感谢那里的许多教程,我能够遍历一组字符串,递归地找到所有排列,然后将它们与英语单词列表进行比较。我发现的问题是,在大约三个词之后(通常是“变形”之类的词),我得到了 OutOfMemory 错误。我尝试将我的批处理分成小集合,因为它似乎是消耗我所有内存的递归部分。但即使只是“变形”也会将其锁定...
这里我从一个文件中读取单词到一个列表中
Scanner scanner = new Scanner(resource.getInputStream());
while (scanner.hasNext()) {
String s = scanner.nextLine();
uniqueWords.add(s.toLowerCase());
}
现在我将它们分解成更小的集合并调用一个类来生成字谜:
List<List<String>> subSets = Lists.partition(new ArrayList(uniqueWords), SET_SIZE);
for (List<String> set: subSets) {
// tried created as class attribute & injection, no difference
AnagramGenerator anagramGenerator = new AnagramGenerator();
List<Word> anagrams = anagramGenerator.createWordList(set);
wordsRepository.save(anagrams);
LOGGER.info("Inserted {} records into the database", anagrams.size());
}
最后是我的发电机:
public class AnagramGenerator {
private Map<String, List<String>> map = new Hashtable<>();
public List<Word> createWordList(List<String> dictionary) {
buildAnagrams(dictionary);
List<Word> words = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
words.add(new Word(entry.getKey(), entry.getValue()));
}
return words;
}
private Map<String, List<String>> buildAnagrams(List<String> dictionary) {
for (String str : dictionary) {
String key = sortString(str);
if (map.get(key) != null) {
map.get(key).add(str.toLowerCase());
} else {
if (str.length() < 2) {
map.put(key, new ArrayList<>());
} else {
Set<String> permutations = permutations(str);
Set<String> anagramList = new HashSet<>();
for (String temp : permutations) {
if (dictionary.contains(temp) && !temp.equalsIgnoreCase(str)) {
anagramList.add(temp);
}
}
map.put(key, new ArrayList<>(anagramList));
}
}
}
return map;
}
private Set<String> permutations(String str) {
if (str.isEmpty()) {
return Collections.singleton(str);
} else {
Set<String> set = new HashSet<>();
for (int i = 0; i < str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i + 1)))
set.add(str.charAt(i) + s);
return set;
}
}
编辑:基于出色的反馈,我将生成器从排列更改为工作查找:
public class AnagramGenerator {
private Map<String, Set<String>> groupedByAnagram = new HashMap<String, Set<String>>();
private Set<String> dictionary;
public AnagramGenerator(Set<String> dictionary) {
this.dictionary = dictionary;
}
public List<Word> searchAlphabetically() {
List<Word> words = new ArrayList<>();
for (String word : dictionary) {
String key = sortString(word);
if (!groupedByAnagram.containsKey(key)) {
groupedByAnagram.put(key, new HashSet<>());
}
if (!word.equalsIgnoreCase(key)) {
groupedByAnagram.get(key).add(word);
}
}
for (Map.Entry<String, Set<String>> entry : groupedByAnagram.entrySet()) {
words.add(new Word(entry.getKey(), new ArrayList(entry.getValue())));
}
return words;
}
private String sortString(String goodString) {
char[] letters = goodString.toLowerCase().toCharArray();
Arrays.sort(letters);
return new String(letters);
}
它有更多的调整,所以我没有添加一个词,因为它是自己的变位词,但除此之外,它看起来非常快。而且,代码更简洁。谢谢大家!
最佳答案
对于较长的单词,排列的数量很快就会变得巨大。
/usr/share/dict/british-english
Debian 上有 99,156 行。单词列表更长,但让我们以此为例。
九个字母的单词的排列数是 9! = 362,880
因此,对于 9 个或更多字母的单词,与尝试输入单词的每个排列相比,尝试字典中的每个单词所需的计算量更少。
10! milliseconds = ~1 hour
12! milliseconds = ~5.54 days
15! milliseconds = ~41.44 years
而且您很幸运能够每毫秒处理一个排列,因此您很快就会发现许多排列是完全不切实际的。对堆栈和堆的影响以相同的速度增加。
所以,试试算法(伪代码):
sorted_input = sort_alphabetically(input_word)
for each dictionary_word // probably a file readline()
sorted_dictionary_word = sort_alphabetically(dictionary_word)
if(sorted_dictionary_word = sorted_input)
it's an anagram! Handle it
end
end
同样,您可以相当快速地将所有字典词算法写入查找数据结构。再次伪代码;在 Java 中你可以使用 Map<String, List<String>>
或 MultiMap
来自 Apache Commons 或 Guava:
multimap = new MultiMap<String, String> // or whatever
def build_dict:
for each dictionary_word // probably a file readline()
multimap.add(
sort_alphabetically(dictionary_word),
dictionary_word)
end
end
def lookup_anagrams(word):
return multimap.get(sort_alphabetically(word))
end
这会占用适量的内存(整个字典,加上一些键和映射开销),但这意味着一旦创建了结构,您就可以非常便宜地一遍又一遍地查询。
如果你想找到两个单词的字谜,你将需要一个更复杂和有趣的算法。但即便如此,避免暴力破解整个排列的搜索空间对您的成功至关重要。
关于Java Anagram 内存不足,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42514068/
我正在寻找一种有效的解决方案来检查两个字符串是否是字谜词,但字符表/字典检查对于 unicode 可能不是一个好的解决方案。我已经提出了一个解决方案,但我不知道如何在数学上证明它是正确的。公式表达为“
这是我的代码,用于判断两个字符串是否是字谜 static boolean isAnagram(String a, String b) { if (a.length() != b.length(
为什么代码向我显示缺少 return 语句的错误? 我想做的是检查字符串的长度及其内容并比较它们。 import java.util.Scanner; public class Solution {
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 6 年前。 Improve this ques
我正在尝试解决古老的字谜问题。感谢那里的许多教程,我能够遍历一组字符串,递归地找到所有排列,然后将它们与英语单词列表进行比较。我发现的问题是,在大约三个词之后(通常是“变形”之类的词),我得到了 Ou
关闭。这个问题需要details or clarity .它目前不接受答案。 想改进这个问题吗? 通过 editing this post 添加细节并澄清问题. 关闭 7 个月前。 Improve
完全披露我是一名正在做家庭作业的大学生。我不一定是在寻找我的问题的直接答案,而是在寻找正确方向的插入力。所以这是我的问题。我必须编写一个接受 2 个命令行参数的 C 程序,一个是包含单词列表的文件,另
我试图执行变位词排序,直到这里我才这样做: 我对数组中的每个string进行了排序,并将其存储到hashmap中。 现在我有一个映射,键是字符串,值是该字符串的变位词。 代码如下: public st
我在 Java 中有一个 Strings 数组。我需要从数组中找到字谜并将它们打印到屏幕上。 我在比较数组元素以检查它们是否是字谜的部分遇到了困难。我该怎么做?显然,我必须创建一个循环才能遍历数组。
我可以弄清楚如何创建字符串的变位词,但我不知道如何将它们与真实单词词典进行比较以检查变位词是否是真实单词。 Java API 中是否有包含整个英语词典的类? 最佳答案 没有,但是你可以从 variou
题目地址:https://leetcode.com/problems/anagrams/#/descriptionopen in new window 题目描述 Given an array of
题目地址:https://leetcode.com/problems/valid-anagram/open in new window Total Accepted: 78186 Total Sub
我有一个分配给一个函数,该函数将接受 2 个字符串并返回需要删除的字符数,以便使 2 个字符串彼此变位。我的问题是这个函数的时间复杂度是多少以及是否有更快的方法来达到相同的结果。这是我的解决方案: f
问题如下: 通过将 CARE 一词中的每个字母分别替换为 1、2、9 和 6,我们形成一个平方数:1296 = 36^(2)。值得注意的是,通过使用相同的数字替换,字谜词 RACE 也形成了一个平方数
我在 Cracking The Coding Interview 书中遇到了这个主题。挑战在于找到给定的较小字符串 s 在较大字符串 b 中的排列。我可以提出以下算法,其时间复杂度为 O(B x S)
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
正如您在标题中看到的,我正在尝试编写一个程序,该程序可以为我解决“晚间标准管测验”。它的一部分。它必须能够在地铁站名称中找到字谜。我在网上找到了很多代码来检查两个单词是否是字谜。但我需要一些不同的东西
我决定为我的父亲制作一个字谜解算器。我对编程很陌生,但我认为我仍然可以做到。我的成品可以用,但是速度确实很慢,例如找到8个字符的所有组合花了大约15分钟以上。我正在寻找对其进行优化/使其更快的方法。
这是一个解决以下问题的程序:“给定两个字符串 和 ,其长度可能相同也可能不同,确定制作 和 字谜所需的最小字符删除数。可以从其中删除任何字符任一字符串”。最后,两个字符串应该具有相同的字母,并且每个字
这是一个 Java 程序,可以在不使用数组的情况下生成和打印四位数字的所有可能的“Anagrams”。到目前为止,这是我能够做的: import java.util.*; class Anag {
我是一名优秀的程序员,十分优秀!