这是一道面试问题（电话面试）：编写一个函数（使用Java语言），在给定的文本中查找给定单词的所有排列。例如，对于单词abc和文本abcxyaxbcayxycab，该函数应返回abc，bca，cab。
我的回答如下：
显然，我可以循环遍历给定单词的所有排列并使用标准的substring函数。然而，编写代码以生成所有单词排列可能有些困难（目前对我来说是这样的）。
更容易的方法是循环遍历单词大小的所有文本子字符串，对每个子字符串进行排序，并将其与“排序后”的给定单词进行比较。我可以立即编写这样的函数。
我可能可以修改一些子字符串搜索算法，但我现在不记得这些算法。
你会如何回答这个问题？
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<needle.length();i++) {
if (curMap.contains(haystack[i])) {
matchedLength++
curMap[haystack[i]]++
}
}
if (matchedLength == needleSize) {
System.out.println("Match found at: 0");
}
//Search itself
for (int i=0;i<haystack.length()-needle.length();i++) {
int targetValue1 = targetMap[haystack[i]]; //Reading from hashmap, O(1)
int curValue1 = curMap[haystack[i]]; //Another read
//If we are removing beneficial character
if (targetValue1 > 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)
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];
}
}
您应该能够在一次遍历中完成此操作。首先建立一个包含要搜索的单词中所有字符的映射。因此，最初的映射包含[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
abcba的情况下，它只会找到abc。如果您想处理重叠的出现次数，可以修改算法，使其在找到匹配项时将索引减去找到的字符串长度减1。这段代码应该可以完成工作：
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<Character> charsActuallyFound = new ArrayList<Character>();
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列表用于跟踪循环中已经找到的字符。这是为了避免匹配“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
进行了一些基准测试，上面的代码在一个随机字符串的 36M 中仅用了 4.5 秒就找到了 30815 个 "abc" 的匹配项。正如 Jim 已经说过的那样，感谢这个谜题...
notYetFounds.indexOf(c.toString()); 使整个算法的复杂度达到了惊人的 O(needle.length()*haystack.length())，因为在你的情况下，indexOf 的复杂度基本上是 O(needle.length())。然而，读/写Map的复杂度是 O(1)。因此，使用Map的算法结果的复杂度为 O(haystack.length())，速度快了一个数量级（特别是对于巨大的needle）。 - bezmaxhaystack="abcba" 和 needle="abc" 会产生两个匹配项：[abc]ba 和 ab[cba]，而你的算法只产生第一个匹配项（然后重置缓冲区）。 - bezmax第二种方法对我来说非常优雅，应该是完全可接受的。我认为它的规模为O(M * N log N)，其中N是单词长度，M是文本长度。
我可以想出一个稍微复杂一些的O(M)算法：
length(word)）执行相同的操作subFreqsubFreq中非零元素的数量，得到numDiffnumDiff等于零，则表示匹配成功subFreq和numDiff编辑：看到已经发布了几个类似的答案。这个算法大部分与其他人建议的滚动频率计数等价。我谦虚地补充了一个滚动方式更新差异数量的方法，从而得到一个O(M+N)算法，而不是O(M*N)。
编辑2：刚刚看到Max在评论中基本上也提出了这个建议，所以给他加分。
O(M+N)，你是否假设读写Map的时间复杂度是O(N)？我认为你的算法是O(M)。对于适合此任务的正确Map实现，读写应该是O(1)。 - bezmax
i=3（子字符串xya）处匹配，则映射将为[a->1, x->1, y->1]。在草堆中前进时，减少haystack[i]的字符计数，并增加haystack[i+needle.length()]的计数。（删除零以确保Map.equals()有效，或者只是实现自定义比较。） - millimoosematchedCharactersCnt的变量会怎样呢？在haystack字符串的开头，将其设为0。每次你将映射“向着”目标值进行更改时 - 增加该变量的值。每次你将映射“远离”目标值进行更改时 - 减少该变量的值。每次迭代时，检查变量是否等于needle字符串的长度。如果是，则找到了匹配项。这比每次完全比较映射要快。 - bezmax