通过最多删除一个字符来检查回文的 JavaScript 算法 - 这种递归方法的时间复杂度

Question

这是 leetcode question这里给你一个字符串s，你最多可以删除一个字符来判断这是否是回文。例如，

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

所以这是我使用递归的解决方案

var validPalindrome = function(s) {
    if(s.trim().length === 0) return true
    
    const isValidPalindrome = (start, end, skipped) => {
        if(skipped > 1) return false
        if(start >= end) return true
        if(s[start] === s[end]) return isValidPalindrome(start+1,end-1, skipped)
        else return isValidPalindrome(start, end - 1, skipped + 1) || isValidPalindrome(start + 1, end, skipped + 1)
    }
    
    return isValidPalindrome(0, s.length - 1, 0)
};

当左右字符不匹配时，您可以跳过一个或另一个，但您不知道是哪个。因此，在这一点上，您只需要探索这两条路径。

但是我很难分析这种递归的时间复杂度。我知道这个解决方案的迭代版本应该有一个 O(n) 运行时。不确定我如何在这里分析时间复杂度。

Answer 1

在所有递归调用中，开始增加和/或结束减少。当 start >= end 时递归停止。因此，在最坏的情况下，每次迭代仅开始或结束更改时，它将递归 end - start = n 次。

正如您已经观察到的，这两个递归调用可能是一个问题，但是随着跳过的次数增加，并且当跳过 > 1 时递归停止，这条路径只会被执行一次。因此，我们可以将代码重写为两个函数，第二个是:

     const isValidPalindromeTailRecursion = (start, end) => {
       if(start >= end) return true
       if(s[start] === s[end]) return isValidPalindrome(start+1,end-1, skipped)
       else return false;
    };

现在确定这个版本的时间复杂度很容易，因为我们只有尾递归:

 T(1) = 1
 T(n) = T(n - 1) + 1 = n

鉴于此，我们可以采用原始函数并重写它:

     const isValidPalindrome = (start, end) => {     
       if(start >= end) return true
       if(s[start] === s[end]) return isValidPalindrome(start+1,end-1)
       else return isValidPalindromeTailRecursion(start, end - 1) || isValidPalindromeTailRecursion(start + 1, end)
    }

现在分析这个就简单多了，我们来看三种情况:

1.) 存在一个有效的回文:

isValidPalindrome 递归遍历字符串，增加每一步的开始和减少结束。因此会有 n/2 次递归步骤。在这种情况下，时间复杂度为 O(n)。

2.) 没有回文，只有第m个字符不同:

isValidPalindrome 递归 m 次，直到找到不同的字符。从那里 isValidPalindromeTailRecursion 被调用两次，并递归到最后(n - m 步)。总共有 m + 2 * (n - m) 个步骤，导致时间复杂度为 O(n)。

3.) 没有回文，多个字符不同:

就像在 2.) isValidPalindrome 递归 m 次直到找到第一个差异，然后 isValidPalindromeTailRecursion 递归两次，直到找到第二个差异，此时算法终止。总共有 m + 2 * (m² - m) 个步骤(其中 m² 是第二次出现的位置)。由于 m, m² < n，这也导致时间复杂度为 O(n)。

因此，该算法总体上是 O(n)。