8/13 每日一題 (通過最多刪除一個元素判斷是否回文)

 Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

class Solution:

    def validPalindrome(self, s: str) -> bool:

        if len(s)<3: #1or2都成立

            return True

        def is_element_same(s,left,right):

            while left < right:

                if s[left] != s[right]:

                    return False

                left +=1

                right -=1                                

            return True

        left,right=0,len(s)-1

        while left<right:

            if s[left] != s[right]:

            #當出現不同元素時嘗試刪除左右邊

                return is_element_same(s,left,right-1) or is_element_same(s,left+1,right)

                #看刪除左或右哪邊可以得到Ture或是同時得到false

            left +=1

            right -=1

        return True

       

#邏輯概要,使用雙指針同時檢查,當遇到不相符的元素時

#分別檢查移除左或右指針,是否仍是回文,

#return is_element_same(s,left,right-1) or is_element_same(s,left+1,right)

#如果兩者其依得到True 那就是回文,當兩者都失敗時 則返回False


-------------參考解答 使用切片

class Solution: def validPalindrome(self, s: str) -> bool: p1=0 p2=len(s)-1 while p1<=p2: if s[p1]!=s[p2]: string1=s[:p1]+s[p1+1:] string2=s[:p2]+s[p2+1:] return string1==string1[::-1] or string2==string2[::-1] p1+=1 p2-=1 return True

-------------------------

class Solution:
    def validPalindrome(self, s: str) -> bool:
        half = len(s)//2+1
        s_rev = s[-half:][::-1]
        if s[:half] == s_rev:
            return True
        for i in range(0, half):
            if s[i] != s_rev[i]:
                return s[i+1:half] == s_rev[i:half-1] or s[i:half-1] == s_rev[i+1:]
        return True

       

----------------------------

class Solution:
    def validPalindrome(self, s: str) -> bool:
        t = s[::-1]
        n = len(s)
        print(t)
        if t == s:
            return True

        for i in range(len(t)):
            if t[i] != s[i]:
                tmp = t[:i] + t[i+1:]
                tmp1 = s[:i] + s[i+1:]
                return tmp == tmp[::-1] or tmp1 == tmp1[::-1]