LeetCode:680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/submissions/

Solution:Array

The goal of this problem is to find the 'the character which needs to be deleted',let's denote it as 'key'. The given string will be shown as a pattern of Palindrome after located and deleted the 'key',

Find the 'key'

We try to check the comparison of head & tail elements of the string, if they are identical characters, check the next pair, otherwise, one of them will be the 'key' we want to find.

(if the length of string is n, in this way, the time complexity can be reduced to n/2 )

Exception:but here is a special scenario will break the algorithm of 'head-tail- comparison',for example: 'abbaa'.

thus we design flow control as:

1. if the 'key' located at head or tail, return True
2. else we begin to execute our 'head-tail-comparison'.

Details of head-tail-comparison

(psuedocode)
if head!=tail:
  Construct a named 'List1'(removded head) 
  Construct a named 'List2'(removded tail)

then:
if ConstructList1==(in reversed ordered)ConstructList1-->return True
if ConstructList2==(in reversed ordered)ConstructList2-->return True

Submission

• faster than 91.08%

class Solution:
    def validPalindrome(self, s: str) -> bool:
#Step1:
        if s[1:] == s[1:][::-1] or s[0:-1] == s[0:-1][::-1]:
            return True
#Step2:
        else:
            for i in range((len(s) + 1) // 2):
                if s[i] != s[-(i + 1)]:
                    check1 = s[0:i] + s[(i + 1):]
                    check2 = s[0: -(i + 1)] + s[-i:]
                    if check1 == check1[::-1] or check2 == check2[::-1]:
                        return True
                    else:
                        return False
            return True