【leetcode刷题】T87-验证回文字符串 Ⅱ
【题目】
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 :
输入: "aba"
输出: True
示例 :
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
【思路】
（我和这道题。。。在面试时认识的，当时，我不认识它，它也不认识我。。。于是，我挂了）
这道题是在说，判断回文串时，我们可以允许有一个字符多余。
使用两个指针i和j前后遍历时，当遇到字符不相同时，再判断s[i+1:j]和s[i:j-1]两者中是否有一个是回文串。
【代码】
python版本
class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
l, r = , len(s) -
while l < r:
if s[l] == s[r]:
l +=
r -=
else:
break
# 是回文串
if l == r:
return True
# 不是回文串，删除一个字符
return s[l+: r+] == s[l+: r+][::-1] or s[l: r] == s[l: r][::-1]
C++版本
void judge(int &l, int &r, string s){
while(l < r){
if(s[l] != s[r])
break;
l++;
r--;
}
}
class Solution {
public:
bool validPalindrome(string s) {
int l=, r=s.size()-1;
judge(l, r, s);
// 是回文串
if(l == r)
return true;
// 不是回文串
int tmpl = l+;
int tmpr = r;
judge(tmpl, tmpr, s);
if(tmpl >= tmpr)
return true;
tmpl = l;
tmpr = r-1;
judge(tmpl, tmpr, s);
if(tmpl >= tmpr)
return true;
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读