这是为文本生成字谜的最佳方法(最多80个字符长度).示例:输入:狗输出狗dgo odg ogd gdo god
我只想到一个回溯解决方案,但如果文本更长,那将需要一段时间.
另一个想法是为字典中的所有单词构建,但问题并不是要求真正的单词.
有人能指出最小时间复杂度解决方案吗？
谢谢!
它实际上是用Java实现的,因为你可以使用Comparator和内置方法对字符数组进行排序并比较这样的字符串:
public class AnagramComparator implements Comparator<String> {
public String sortChars(String s) {
char[] content = s.toCharArray();
Arrays.sort(content);
return new String(content);
}
public int compare(String s1, String s2) {
return sortChars(s1).compareTo(sortChars(s2));
}
}
但我想知道如何在C++中实现它？编写上述Java代码中使用的内置方法的C++等价物绝对是一种选择.还有其他智能方式吗？
我想出了下面的程序来检查两个字符串是否是字谜.它适用于小字符串,但适用于较大的字符串(我试过:听过,入伍)它给我一个'不!'
救命 !
#include<iostream.h>
#include<string.h>
#include<stdio.h>
int main()
{
char str1[100], str2[100];
gets(str1);
gets(str2);
int i,j;
int n1=strlen(str1);
int n2=strlen(str2);
int c=0;
if(n1!=n2)
{
cout<<"\nThey are not anagrams ! ";
return 0;
}
else
{
for(i=0;i<n1;i++)
for(j=0;j<n2;j++)
if(str1[i]==str2[j])
++c;
}
if(c==n1)
cout<<"yes ! anagram !! ";
else
cout<<"no ! ";
system("pause");
return 0;
}
让我说我有一个像这样的列表
狗dOg上帝狗狗狗斑马木头
我想要做的是查找列表中的所有单词,无论是否大小写,或者无论实际单词如何.我想匹配这些字母并计算一下.从上面来说
狗,dOg,上帝都会成为一个匹配,在这种情况下会返回"3"作为计数,但是狗,狗,斑马,木头..都将是独一无二的,所有人都将返回1作为计数..虽然我知道这是可能的我不知道从哪里开始.anagram概念让我有点失望.有任何想法吗？
我在一些SO帖子上看到要乱洗数组,你会使用php的shuffle($array);.
但是,我的问题是我从字典中生成一个随机单词(我知道该怎么做并且正在工作),然后将这些字母随机地变成一个字谜.
所以基本上 - 这个词random会adrmon或类似的东西,但它会随机抽取单词中的字母.
我怎么能在PHP中这样做？
我最近一直在玩Ruby,我刚从http://codekata.pragprog.com完成了Anagrams Code Kata .
该解决方案是测试驱动的,并利用独特的素因子化定理,但它似乎运行得非常慢.就45k文件而言,到目前为止它已经运行了大约10分钟.任何人都可以给我任何关于提高代码性能的指示吗？
class AnagramFinder
def initialize
@words = self.LoadWordsFromFile("dict45k.txt")
end
def OutputAnagrams
hash = self.CalculatePrimeValueHash
@words.each_index{|i|
word = @words[i]
wordvalue = hash[i]
matches = hash.select{|key,value| value == wordvalue}
if(matches.length > 1)
puts("--------------")
matches.each{|key,value|
puts(@words[key])
}
end
}
end
def CalculatePrimeValueHash
hash = Hash.new
@words.each_index{|i|
word = @words[i]
value = self.CalculatePrimeWordValue(word)
hash[i] = value
}
hash
end
def CalculatePrimeWordValue(word)
total = 1
hash = self.GetPrimeAlphabetHash
word.downcase.each_char {|c|
value = hash[c]
total = total * value
} …我想解决下面的问题:
anagram是一种文字游戏,是重新排列单词或短语的字母以产生新单词或短语的结果,使用所有原始字母恰好一次; 例如,orchestra = carthorse.使用http://www.puzzlers.org/pub/wordlists/unixdict.txt中的单词列表,编写一个程序,查找共享包含最多单词的相同字符的单词集.
即使只有1000字节的文件大小,它也会失败.每次创建新列表时,为什么Python会将旧列表保留在内存中？我收到以下错误.
l=list(map(''.join, itertools.permutations(i)))
给我:
MemoryError
这是我的代码:
import itertools
def anagram():
f=open('unixdict.txt')
f2=open('result_anagram.txt','w')
words = f.read(1000).split('\n')
for i in words:
l=[]
l=list(map(''.join, itertools.permutations(i)))
l.remove(i)
for anagram in l:
if l==i:
f2.write(i + "\n")
return True
anagram()
根据建议将上述代码更改为.但仍然得到内存错误.
import itertools
def anagram():
f=open('unixdict.txt')
f2=open('result_anagram.txt','w')
words = set(line.rstrip('\n') for line in f)
for i in words:
l= map(''.join, itertools.permutations(i))
l =(x for x in l if x!=i)
for anagram in l:
if anagram in words:
f2.write(i …我正在尝试编写一个anagram程序,所以我找到了以下示例.但是我无法弄清楚这一行,first[a[i]-'a']++; 在这里增加这个char数组的值有什么意义呢？
#include <stdio.h>
int check_anagram(char a[], char b[]){
int first[26] = {0}, second[26] = {0}, i = 0;
while (a[i] != '\0'){
first[a[i]-'a']++; // ??????????
i++;
}
i = 0;
while (b[i] != '\0'){
second[b[i]-'a']++;
i++;
}
for (i = 0; i < 26; i++){
if (first[i] != second[i])
return 0;
}
return 1;
}
int main(){
char a[100], b[100];
int flag;
printf("Enter first string\n");
gets(a);
printf("Enter second string\n");
gets(b);
flag = check_anagram(a, b);
if (flag == 1) …我编写了一个 Java 程序来查找 2 个字符串的 Anagram。
供参考：如果两个字符串使用完全相同的字母书写，忽略空格、标点符号和大写，则它们是字谜词。每个字母在两个字符串中的计数应该相同。例如，Army 和 Mary 是彼此的变位词。
程序：
package practice;
import java.util.ArrayList;
import java.util.List;
public class Anagram_String {
public static void main(String[] args) {
String s1="mary";
String s2="army";
int k=0;
List<String> matchedChar= new ArrayList<String>();
String charmatch="";
char[] ch1= s1.toLowerCase().toCharArray();
char[] ch2= s2.toLowerCase().toCharArray();
if(s1.length()==s2.length())
{
for(int i=0;i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
if(ch1[i]==ch2[j])
{
k++;
charmatch=String.valueOf(ch1[i]);
System.out.println(charmatch);
matchedChar.add(charmatch);
System.out.println("Arraylist value is "+matchedChar.toString());
System.out.println(matchedChar.size());
}
}
k=0;
}
String arrayValue=matchedChar.toString();
System.out.println("Array value is "+arrayValue);
if(arrayValue.contains(s2)){
System.out.println("String 1 and String 2 …我正在努力解决古老的anagram问题.感谢那里的许多教程,我能够遍历一组字符串,递归地找到所有排列,然后将它们与英语单词列表进行比较.我发现的问题是,在大约三个单词(通常是"变态"之类的东西)之后,我得到一个OutOfMemory错误.我尝试将我的批次分成小集,因为它似乎是消耗我所有记忆的递归部分.但即便只是"变态"锁定它......
在这里,我将文件中的单词读入List
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 …