很久没有做题了,今天写个简单难度的练练手感。
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
分析:这个题目的要求是判断回文,但是增加了一点难度,可以删掉至多一个字符。所以,我们可以从字符串的两头往中间进行每个字符的比较。先比较s[0]和s[len(s)-1],如果相同的话,低位+1,高位-1,直到找到两个字符不同为止。因为可以删除一个字符,所以还需要判断s[低位+1] == s[高位] 和 s[低位] == s[高位-1],如果满足其中一个条件,那么对应位置+1或者-1继续比较。如果两个都满足,我的方法是先比较s[低位] == s[高位-1],如果不是回文,再来比较s[低位+1] == s[高位]。
代码:
class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
low = 0;
high = len(s)-1
isDel = False
fisrtFlag = false
firstLow = 0
firstHigh = 0
ret = True
while low < high:
if s[low] == s[high]:
low += 1
high -= 1
continue
else:
if isDel == True:
ret = False
break
if s[low] != s[high-1] and s[low+1] != s[high]:
ret = False
break
elif s[low] == s[high-1]:
firstLow = low
firstHigh = high-1
fisrtFlag = True
high -= 1
isDel = True
elif s[low+1] == s[high]:
low += 1
isDel = True
#再比较异常
if ret == False and fisrtFlag == True:
ret = True
low = firstLow + 1
high = firstHigh + 1
while low < high:
if s[low] == s[high]:
low += 1
high -= 1
continue
else:
ret = False
break
return ret