[LeetCode] Valid Palindrome II 验证回文字符串之二
2024-10-19 03:26:42
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.
这道题是之前那道Valid Palindrome的拓展,还是让我们验证回复字符串,但是区别是这道题的字符串中只含有小写字母,而且这道题允许删除一个字符,那么当遇到不匹配的时候,我们到底是删除左边的字符,还是右边的字符呢,我们的做法是两种情况都要算一遍,只要有一种能返回true,那么结果就返回true。我们可以写一个子函数来判断字符串中的某一个范围内的子字符串是否为回文串,参见代码如下:
解法一:
class Solution {
public:
bool validPalindrome(string s) {
int left = , right = s.size() - ;
while (left < right) {
if (s[left] != s[right]) return isValid(s, left, right - ) || isValid(s, left + , right);
++left; --right;
}
return true;
}
bool isValid(string s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
++left; --right;
}
return true;
}
};
下面这种写法跟上面的解法思路一样,只不过没有写额外的函数,还是要遍历两种情况,参见代码如下:
解法二:
class Solution {
public:
bool validPalindrome(string s) {
int left = , right = s.size() - ;
while (left < right) {
if (s[left] == s[right]) {
++left; --right;
} else {
int l = left, r = right - ;
while (l < r) {
if (s[l] != s[r]) break;
++l; --r;
if (l >= r) return true;
}
++left;
while (left < right) {
if (s[left] != s[right]) return false;
++left; --right;
}
}
}
return true;
}
};
类似题目:
参考资料:
https://discuss.leetcode.com/topic/103939/java-o-n-time-o-1-space
https://discuss.leetcode.com/topic/103911/two-solutions-optimized-and-recursive-java-and-c
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- .NET跨平台之旅:将示例站点升级至 ASP.NET Core 1.1
- js自定义验证码
- C# 开源框架
- ESP8266刷AT固件与nodemcu固件
- 手机支持USB功能、驱动文件对应关系
- third class
- jar-下载站点
- [c#]RabbitMQ的简单使用
- Codeforces Round #336 (Div. 2) D. Zuma 记忆化搜索
- QL Server 中四种匹配符的含义
- wikioi 1044 拦截导弹 (1999年NOIP全国联赛提高组)
- unbuntu下的root 用户和 sudo 命令
- hdu_3247_Resource Archiver(AC自动机+bfs+TSP)
- Block使用的简单总结
- java中List按指定大小分割
- python3 输出系统信息
- git中工作区,缓存区,本地库,远程库的简要区别
- mongodb 数据库操作--备份 还原 导出 导入(转)
- 【洛谷】3469:[POI2008]BLO-Blockade【割点统计size】
- Cisco配置发送日志到日志服务器