Whenever there is a mismatch when checking for palindrome, we try deleting either one of the two characters involved in the mismatch and see if isPalindrome succeeds. To make sure, we don’t delete more than 1 character, we also maintain the delCount.
def isPalindrome(self, s, start, end, delCount): if delCount > 1: return False while start < end: if s[start] != s[end]: break start += 1 end -= 1 if (start == end) or (start == end+1): return True return any([self.isPalindrome(s, start+1, end, delCount+1), self.isPalindrome(s, start, end-1, delCount+1)]) def validPalindrome(self, s): return self.isPalindrome(s, 0, len(s)-1, 0)
nice and clever. I guess it is O(n) time where it checks each character only once and also despite recursion it is O(1) because recursion depth can not exceed 2. Nice one!
@sha256pki Thanks :)