这个字符串搜索算法可以优化吗？

Question

最近，我尝试在一个流行的编码网站上进行“测试”，该网站提出了以下问题：

在给定的字符串s中，找到包含最多元音的、大小为k的子串。

例子

s =“eirowpfmsnaq uisaa ”且k = 5 -

• 第 1 遍 - 子字符串 =“eirow” - 元音 = 3

• 第 2 遍 - 子字符串 =“irowp” - 元音 = 2

• 第 3 遍 - 子字符串 =“rowpf” - 元音 = 1

• 第 4 遍 - 子字符串 =“owpfm” - 元音 = 1

• 第 5 遍 - 子串 = "wpfms" - 元音 = 0

• 第 6 遍 - 子字符串 = "pfmsn" - 元音 = 0

• 第 7 遍 - 子字符串 =“fmsna” - 元音 = 1

• 第 8 遍 - 子字符串 =“msnaq” - 元音 = 1

• 第 9 遍 - 子字符串 =“snaqu” - 元音 = 2

• 第 10 遍 - 子字符串 =“naqui” - 元音 = 3

• 第 11 遍 - 子字符串 =“aquis” - 元音 = 3

• 第 12 遍 - 子字符串 =“quisa” - 元音 = 3

• 第 13 遍 - 子字符串 =“uisaa” - 元音 = 4（最终结果）

我创建了一个初始的简单迭代函数，它只是从 0 迭代到字符串长度减去子字符串的长度（i=0 到 i<s.length-k）

const countVowels = str => str.length - str.replace((/[aeiouAEIOU]/gi), "").length

let findSubstring = (s,k) => {

  let max = 0, dict = {}

  for(let i=0;i<=s.length-k;i++) { // iterate over string length - k

    dict[i] = countVowels(s.slice(i, k+i)) // add vowels in substring to dict

    if(dict[i] > dict[max]) max = i // if there are more vowels than the max encountered this is the new max

  }

  return max === 0 ? "Not found!" : s.slice(max, max+k); // return substring if found

}

我发现此方法对于某些测试用例是成功的，但在 10 秒超时和较大输入的情况下多次失败。

作为第二次尝试，我决定将元音计数从循环中删除，并使用映射对于较大的输入来说会更快。由于 V2 中计算最终结果的额外开销，对于较小的输入，第一次尝试会更快。

作为对较小值（例如s长度小于 500、k小于 100）的比较，V1 的性能将优于 V2 9/10 倍。然而，一旦s的长度超过 500 并且k超过 100，您可以看到 V2 优于 V1，并且性能裕度随着s和k变大而增长（正如您所期望的）

然而，我发现当使用 V2 时，我的测试仍然由于超时而失败。我看不到 V2 中可以进行任何更改以显着优化它，因此我很想知道是否有人有任何想法可以使其更快地处理大量输入。

Answer 1

像这样的东西会快得多，它只是一次 O(1) 查找的线性传递：def count_vowels(s, k):&nbsp; &nbsp; vowels = set("aeiouAEIOU")&nbsp; &nbsp; #count first k&nbsp; &nbsp; t = sum(1 for i in s[:k] if i in vowels)&nbsp; &nbsp; mx = t&nbsp; &nbsp; for i in range(k, len(s)):&nbsp; &nbsp; &nbsp; &nbsp; if s[i] in vowels:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t+=1&nbsp; &nbsp; &nbsp; &nbsp; if s[i-k] in vowels:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t-=1&nbsp; &nbsp; &nbsp; &nbsp; if t > mx:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mx = t&nbsp; &nbsp; return mxcount_vowels("eirowpfmsnaquisaaaa",5)下面是如何在 JavaScript 中实现这一点：function count_vowels(s, k) {&nbsp; const vowels = new Set(Array.from("aeiouAEIOU"));&nbsp; let t = 0;&nbsp; //count first k&nbsp; for (let i = 0; i < k && i < s.length; i++) {&nbsp; &nbsp; t += vowels.has(s[i]) ? 1 : 0;&nbsp; }&nbsp; let mx = t;&nbsp; for (let i = k; i < s.length; i++) {&nbsp; &nbsp; if (vowels.has(s[i])) {&nbsp; &nbsp; &nbsp; t += 1&nbsp; &nbsp; }&nbsp; &nbsp; if (vowels.has(s[i - k])) {&nbsp; &nbsp; &nbsp; t -= 1;&nbsp; &nbsp; }&nbsp; &nbsp; if (t > mx) {&nbsp; &nbsp; &nbsp; mx = t;&nbsp; &nbsp; }&nbsp; }&nbsp; return mx;}console.log(count_vowels("eirowpfmsnaquisaaaa", 5))