这是 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)
运行时。不确定我如何在这里分析时间复杂度。
最佳答案
在所有递归调用中,开始增加和/或结束减少。当 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)。
关于通过最多删除一个字符来检查回文的 JavaScript 算法 - 这种递归方法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66737484/