我一直在尝试找到以下问题的O（n）解决方案：在字符串b中查找字符串s的字谜（排列）数，其中s.length始终小于b.length
我读到最佳解决方案包括跟踪较小字符串中的字符频率，并在滑动窗口跨较大字符串移动时对它进行相同的操作，但是我不确定该实现实际上如何工作。现在，我的解决方案不起作用（请参阅评论），但即使可行，也将花费O（s + sn）的时间。
编辑：示例输入：('aba', 'abaab')。输出：3，因为'aba'存在于b中，从索引0，索引'baa'1和索引'aab'2开始。
function anagramsInStr(s,b) {
//O(s)
let freq = s.split("").reduce((map, el) => {
map[el] = (map[el] + 1) || 1;
return map;
}, {});
let i = 0, j = s.length;
// O(n)
for (let char in b.split("")) {
// O(s)
if (b.length - char + 1 > s.length) {
let window = b.slice(i,j);
let windowFreq = window.split("").reduce((map, el) => {
map[el] = (map[el] + 1) || 1;
return map;
}, {});
// Somewhere about here compare the frequencies of chars found in the window to the frequencies hash defined in the outer scope.
i++;
j++;
}
}
}
仔细阅读评论，如果您有任何疑问，请告诉我：
function countAnagramOccurrences(s, b) {
var matchCount = 0;
var sCounts = {}; // counts for the letters in s
var bCounts = {}; // counts for the letters in b
// construct sCounts
for (var i = 0; i < s.length; i++) {
sCounts[s[i]] = (sCounts[s[i]] || 0) + 1;
}
// all letters that occur in sCounts
var letters = Object.keys(sCounts);
// for each letter in b
for (var i = 0; i < b.length; i++) {
// maintain a sliding window
// if we already have s.length items in the counts, remove the oldest one
if (i >= s.length) {
bCounts[b[i-s.length]] -= 1;
}
// increment the count for the letter we're currently looking at
bCounts[b[i]] = (bCounts[b[i]] || 0) + 1;
// test for a match (b counts == s counts)
var match = true;
for (var j = 0; j < letters.length; j++) {
if (sCounts[letters[j]] !== bCounts[letters[j]]) {
match = false;
break;
}
}
if (match) {
matchCount += 1;
}
}
return matchCount;
}
console.log(countAnagramOccurrences('aba', 'abaab')); // 3编辑
关于运行时的注释：这是O（nk + m）的一种，其中n是s的长度，m是b的长度，k是b中唯一字符的数量。由于m总是小于n，我们可以减小为O（nk），并且由于k由固定常数（字母的大小）限制，所以我们可以进一步减小为O（n）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句