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

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), "").lengthlet 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):

    vowels = set("aeiouAEIOU")

    #count first k

    t = sum(1 for i in s[:k] if i in vowels)

    mx = t

    for i in range(k, len(s)):

        if s[i] in vowels:

            t+=1

        if s[i-k] in vowels:

            t-=1

        if t > mx:

            mx = t

    return mx

count_vowels("eirowpfmsnaquisaaaa",5)

下面是如何在 JavaScript 中实现这一点：

function count_vowels(s, k) {

  const vowels = new Set(Array.from("aeiouAEIOU"));

  let t = 0;

  //count first k

  for (let i = 0; i < k && i < s.length; i++) {

    t += vowels.has(s[i]) ? 1 : 0;

  }

  let mx = t;

  for (let i = k; i < s.length; i++) {

    if (vowels.has(s[i])) {

      t += 1

    }

    if (vowels.has(s[i - k])) {

      t -= 1;

    }

    if (t > mx) {

      mx = t;

    }

  }

  return mx;

}

console.log(count_vowels("eirowpfmsnaquisaaaa", 5))