如何查找给定文本中给定单词的所有排列？

这是一个面试问题（电话屏幕）：编写一个函数（用Java）来查找给定文本中出现的给定单词的所有排列。 例如，对于单词abc和text abcxyaxbcayxycab该函数应返回abc, bca, cab abcxyaxbcayxycab abc, bca, cab 。

我会回答这个问题如下：

• 显然，我可以遍历给定单词的所有排列并使用标准substring函数。 但是（现在对我来说）编写代码以生成所有单词排列可能很困难。

• 循环遍历单词大小的所有文本子字符串，对每个子字符串进行排序并将其与“已排序”的给定单词进行比较更容易。 我可以立即编写这样的函数。

• 我可以修改一些子串搜索算法，但我现在不记得这些算法了。

你会如何回答这个问题？

Answer 1

这可能不是算法上最有效的解决方案，但从类设计的角度来看它是干净的。 该解决方案采用比较“已排序”给定单词的方法。

如果一个单词包含相同数字的相同字母，我们可以说一个单词是另一个单词的排列。 这意味着您可以将单词从String转换为Map 。 这种转换将具有复杂度O（n），其中n是String的长度，假设Map实现中的插入花费O（1）。

Map将包含在单词中找到的所有字符作为键，并作为值的字符频率。

例子 。 abbc转换为[a->1, b->2, c->1]

bacb转换为[a->1, b->2, c->1]

因此，如果您必须知道两个单词是否是另一个单词的排列，您可以将它们转换为映射，然后调用Map.equals 。

然后，您必须遍历文本字符串并将转换应用于您要查找的相同长度的所有子字符串。

Inerdial提出的改进

通过以“滚动”方式更新Map可以改进这种方法。

即如果你在OP（子串xya ）中的示例haystack中的索引i=3处匹配，则映射将是[a->1, x->1, y->1] 。 当在干草堆中前进时，减少haystack[i]的字符数，并递增haystack[i+needle.length()]的计数。

（删除零以确保Map.equals()有效，或者只是实现自定义比较。）

Max提出的改进

如果我们还引入了matchedCharactersCnt变量怎么办？ 在干草堆的开头它将是0 。 每次将地图更改为所需的值时 – 都会增加变量。 每次将其从期望值更改时 – 您将减少变量。 每次迭代检查变量是否等于针的长度。 如果是 – 你找到了匹配。 它比每次比较完整的地图要快。

Max提供的伪代码：

 needle = "abbc" text = "abbcbbabbcaabbca" needleSize = needle.length() //Map of needle character counts targetMap = [a->1, b->2, c->1] matchedLength = 0 curMap = [a->0, b->0, c->0] //Initial map initialization for (int i=0;i 0 && curValue1 > 0 && curValue1 <= targetValue1) { matchedLength--; } curMap[haystack[i]] = curValue1 + 1; //Write to hashmap, O(1) int targetValue2 = targetMap[haystack[i+needle.length()]] //Read int curValue2 = curMap[haystack[i+needle.length()]] //Read //We are adding a beneficial character if (targetValue2 > 0 && curValue2 < targetValue2) { //If we don't need this letter at all, the amount of matched letters decreases matchedLength++; } curMap[haystack[i+needle.length()]] = curValue2 + 1; //Write if (matchedLength == needleSize) { System.out.println("Match found at: "+(i+1)); } } //Basically with 4 reads and 2 writes which are //independent of the size of the needle, //we get to the maximal possible performance: O(n) 

Answer 2

要查找字符串的排列，可以使用数论。 但是，在使用此算法回答问题之前，您必须事先知道此算法背后的“理论”。

有一种方法可以使用素数计算字符串的哈希值。 相同字符串的每个排列都将给出相同的散列值。 所有其他不是排列的字符串组合将给出一些其他哈希值。

哈希值由c ₁ * p ₁ + c ₂ * p ₂ + … + c _n * p _n计算 ，其中c _i是字符串中当前char的唯一值，其中p _i是唯一素数c _i char的数字值。

这是实施。

 public class Main { static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 }; public static void main(String[] args) { final char[] text = "abcxaaabbbccyaxbcayaaaxycab" .toCharArray(); char[] abc = new char[]{'a','b','c'}; int match = val(abc); for (int i = 0; i < text.length - 2; i++) { char[] _123 = new char[]{text[i],text[i+1],text[i+2]}; if(val(_123)==match){ System.out.println(new String(_123) ); } } } static int p(char c) { return primes[(int)c - (int)'a']; } static int val(char[] cs) { return p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2]; } } 

这个输出是：abc bca cab

Answer 3

你应该能够一次性完成这项工作。 首先构建一个包含您要搜索的单词中所有字符的地图。 所以最初地图包含[a, b, c] 。

现在，一次翻阅一个字符。 循环看起来像这样，在伪代码中。

 found_string = ""; for each character in text if character is in map remove character from map append character to found_string if map is empty output found_string found_string = "" add all characters back to map end if else // not a permutation of the string you're searching for refresh map with characters from found_string found_string = "" end if end for 

如果您想要唯一的出现，请更改输出步骤，以便将找到的字符串添加到地图中。 这将消除重复。

存在包含重复字母的单词的问题。 如果这是一个问题，请将密钥作为字母和值计数。 ‘删除’一个字符意味着减少它在地图中的计数。 如果计数变为0，则该字符实际上已从地图中删除。

写入的算法不会发现重叠事件。 也就是说，给定文本abcba ，它只会找到abc 。 如果要处理重叠事件，可以修改算法，以便在找到匹配时，将索引减1，减去找到的字符串的长度。

这是一个有趣的谜题。 谢谢。

Answer 4

这就是我要做的 – 设置一个标志数组，其中一个元素等于0或1，以指示STR中的该字符是否已匹配

将第一个结果字符串RESULT设置为空。

对于TEXT中的每个字符C：

将数组X等于STR的长度设置为全零。

对于STR中的每个字符S：如果C是STR中的JTH字符，并且X [J] == 0，则设置X [J] <= 1并将C添加到RESULT。 如果RESULT的长度等于STR，则将RESULT添加到排列列表中，并将X []的元素再次设置为零。

如果C不是STR中具有X [J] == 0的任何字符J，则将X []的元素再次设置为零。

Answer 5

第二种方法对我来说似乎非常优雅，应该是完全可以接受的。 我认为它在O(M * N log N)处缩放，其中N是字长， M是文本长度。

我可以想出一个更复杂的O(M)算法：

1. 计算单词中每个字符的出现次数
2. 对文本的前N个（即length(word) ）字符执行相同的操作
3. 减去两个频率向量，得到subFreq
4. 计算subFreq中subFreq ，得到numDiff
5. 如果numDiff等于零，则匹配
6. 通过更新文本中的第一个和后一个字符，在常量时间内更新subFreq和numDiff
7. 转到5直到到达文本末尾

编辑 ：看到几个类似的答案已经发布。 大多数此算法相当于其他人建议的滚动频率计数。 我的简单补充也是以滚动方式更新差异的数量，产生O(M+N)算法而不是O(M*N)算法。

EDIT2 ：刚才看到Max在评论中已基本提出这个问题，所以布朗尼指向他。

Answer 6

这段代码应该做的工作：

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String word = "abc"; final String text = "abcxaaabbbccyaxbcayxycab"; List charsActuallyFound = new ArrayList(); StringBuilder match = new StringBuilder(3); for (Character c : text.toCharArray()) { if (word.contains(c.toString()) && !charsActuallyFound.contains(c)) { charsActuallyFound.add(c); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); charsActuallyFound.clear(); } } else { match = new StringBuilder(3); charsActuallyFound.clear(); } } } } 

charsActuallyFound List用于跟踪已在循环中找到的字符。 需要避免使用“aaa”“bbb”“ccc”（由我添加到您指定的文本中）。

经过进一步思考后，我认为只有给定单词没有重复字符时，我的代码才有效。 上面的代码正确打印

 abc bca cab 

但如果您使用“aaa”这个单词，则不会打印任何内容，因为每个字符不能匹配多次。 灵感来自Jim Mischel的回答，我编辑了我的代码，结尾于此：

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String text = "abcxaaabbbccyaxbcayaaaxycab"; printMatches("aaa", text); printMatches("abc", text); } private static void printMatches(String word, String text) { System.out.println("matches for "+word +" in "+text+":"); StringBuilder match = new StringBuilder(3); StringBuilder notYetFounds=new StringBuilder(word); for (Character c : text.toCharArray()) { int idx = notYetFounds.indexOf(c.toString()); if (idx!=-1) { notYetFounds.replace(idx,idx+1,""); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } else { match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } System.out.println(); } } 

这给了我以下输出：

 matches for aaa in abcxaaabbbccyaxbcayaaaxycab: aaa aaa matches for abc in abcxaaabbbccyaxbcayaaaxycab: abc bca cab 

做了一些基准测试，上面的代码在短短的4.5秒内在36M的随机字符串中找到了30815匹配的“abc”。 正如吉姆已经说过的，感谢这个难题……