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

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

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

JavaScript algorithm to check for Palindrome by deleting at most one character - time complexity for this recursive approach

javascript

algorithm

big-o