给定一个字符串数组,返回作为字谜的所有字符串组.
我的解决方案
对于数组中的每个字符串字,将其排序为O(m lg m),m是字的平均长度.
构建哈希表<string,list>.
将排序后的单词作为键放入哈希表中,并生成单词的所有排列(O(m!)),使用O(m)搜索字典中的每个排列(前缀树映射),如果它在字典中,将(O(1))放入哈希表中,以便将所有排列的单词放入具有相同键的列表中.
总共有O(n*m*lg m*m!)时间和O(n*m!)空间,n是给定数组的大小.
如果m非常大,那就没有效率了,m!.
更好的解决方案？
谢谢
假设我们有一个约250,000字的字典.算法应该将12个字母作为数组或字符串,并找到与字典中最长单词匹配的变体.
当然,人们总是可以蛮力,但我想知道最优雅的方式是什么？
如果不使用任何特定于语言的函数作为主要问题的快捷方式,则也将接受使用PHP以外的语言的答案.
注意:单词存储在数据库中,但我可以将它们拉入内存以提高速度.虽然我不确定PHP的索引是否优于MySQL数据库？
我有一个单词列表和一个包含许多字谜的文件.这些字谜是单词列表中的单词.我需要开发一种算法来查找匹配的单词并在输出文件中生成它们.到目前为止我开发的代码只适用于前两个单词.另外,我无法让代码与包含数字的字符串一起玩得很好.请告诉我如何修复代码.
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main (void)
{
int x = 0, y = 0;
int a = 0, b = 0;
int emptyx, emptyy;
int match = 0;
ifstream f1, f2;
ofstream f3;
string line, line1[1500], line2[50];
size_t found;
f1.open ("wordlist.txt");
f2.open ("file.txt");
f3.open ("output.txt");
while (f1.eof() == 0)
{
getline (f1, line);
line1[x] = line;
x++;
}
while (f2.eof() == 0)
{
getline (f2, line);
line2[y] = line;
y++;
}
//finds position …我接受过关于字谜的练习,看起来很容易让我怀疑我错过了什么.我实施的解决方案是我即将提出的解决方案,我想问你是否可以考虑使用我的解决方案进行任何优化,改变方法或问题.我用Java实现了算法.
现在,练习.作为输入我有一个文本作为输出我应该返回这个文本的每一行是否是每一行的一个字谜.也就是说,输入:
一辆出租车契约最疯狂的小鱼L L
A Cab De Hu Hu Min
A A A A A A A A A A A Mill Mill
Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill …
我有一个字符池,我希望使用正则表达式匹配所有字符的字符,这些字符是那些字符的字符或这些字符的子集.
示例:给定字符串"ACNE",正则表达式应该给我这些结果:
我尝试过这个解决方案,/b[acne]{1,4}/b但它接受多次重复的单个字符.我最多只能一次拿走每个字符？
假设有一个单词集,我想根据他们的char包(multiset)对它们进行聚类.例如
{茶,吃,阿巴,阿巴,你好}
将聚集成
{{tea,eat},{abba,aabb},{hello}}.
abbaaabb由于它们具有相同的char包,即两个a和两个,因此聚集在一起b.
为了使它高效,我能想到的一种天真的方式是将每个单词转换成一个char-cnt系列,例如,abba并且aabb将被转换为a2b2,tea/eat将被转换为a1e1t1.这样我就可以构建一个字典并用相同的键组合单词.
这里有两个问题:首先我必须对字符进行排序以构建密钥; 第二,字符串键看起来很笨拙,性能不如char/int键.
有没有更有效的方法来解决问题？
我正在尝试为swift构建一个anagram检查器.这是我的代码.如果您不知道anagram检查器检查两个字符串是否包含相同的字符,但顺序无关紧要.
func checkForAnagram(#firstString: String, #secondString: String) -> Bool {
var firstStringArray: [Character] = []
var secondStringArray: [Character] = []
/* if case matters delete the next four lines
and make sure your variables are not constants */
var first = firstString
var second = secondString
first = first.lowercaseString
second = second.lowercaseString
for charactersOne in first {
firstStringArray += [charactersOne]
}
for charactersTwo in second {
secondStringArray += [charactersTwo]
}
if firstStringArray.count != secondStringArray.count {
return false
} else {
for …我需要制作一个程序，将带有字典和任意字符串的文件作为输入，然后输出该字典中构成给定字符串的字谜词的所有单词组合。例如，使用英语中 100 个最流行的单词和字符串"i not work"，我应该得到类似 的结果[' on it work', ' into work', ' not i work', ' know or it', ' work it no', ' to work in']，我就是这么做的。
问题是我的程序效率太低：字典中有 100 个单词，字符串长度的实际限制是 7 个字符，之后的所有内容都需要太长的时间。我尝试寻找与此事相关的各种算法但无济于事。
以下是我搜索字谜词的方法：
def sortstring(string):
return ''.join(sorted(string))
def simplify(all_strings):
possible_strings = defaultdict(list)
for string in all_strings:
possible_strings[sortstring(string).strip()].append(string)
return possible_strings
def generate(database, length,curstring="", curdata=set()):
if len(curstring.replace(" ", "")) > length:
return set()
if len((curstring).replace(" ", "")) == length:
return curdata.union(set([curstring]))
for i in database:
if len((curstring+i).replace(" …你可以发现,如果两个字符串是O(nlogn)时间排序两个字符串后字谜,但是有没有可能找到它在O(n)的时间和O(1)空间.
所以我知道找到字谜背后的理论，显示在这里。出于我的目的，我需要找到可以从一个单词中找到的 anagrams 的数量排除重复。
允许重复，这相当简单。
aab有以下字谜：
aab
aab
aba
aba
baa
baa
这个数量可以通过计算字母数量的阶乘来找到
factorial := 1
for i := len(word); i > 0; i-- {
factorial = i * factorial
}
// aab -> 6
但是，如果您想排除重复项，您已将潜在的字谜从 6 个减少到 3 个。一个例子是单词hello，它有 120 个组合，但只有 60 个没有重复项。
我编写了自己的算法来制作字母映射并返回映射的长度，但这也有问题。
hello -> 24 (actually 60)
helllo -> 24 (actually 120)
我怎样才能做到这一点？