680. Valid Palindrome II【easy】
2024-08-29 11:39:25
680. Valid Palindrome II【easy】
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.
错误解法：
class Solution {
public:
bool validPalindrome(string s) {
int start = ;
int end = s.length() - ;
int flag = false;
while (start <= end) {
if (s[start] == s[end]) {
++start;
--end;
}
else {
if (!flag) {
flag = true;
if (s[start + ] == s[end]) {
++start;
} else if (s[start] == s[end - ]) {
--end;
} else {
return false;
}
}
else {
return false;
}
}
}
return true;
}
};
没有通过以下测试用例：
"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"
考察代码逻辑，发现一开始我们命中了
s[start + 1] == s[end]
这个逻辑，"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"，并且设置了标志位，这就坑了，下次发现不相等的情况，就直接返回false了。
其实我们本意是要命中下面的逻辑
s[start] == s[end - 1]
"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"，并且设置了标志位，这样就可以满足测试用例。
就是说每次我们用
s[start + 1] == s[end]
和
s[start] == s[end - 1]
其实是一种“或”的关系，所以我们要一判断就判断到底，比如下面的解法一。
解法一：
class Solution {
public boolean validPalindrome(String s)
{
int left = , right = s.length() - ;
while (left < right)
{
if (s.charAt(left) == s.charAt(right))
{
left++; right--;
}
else
{
//remove right
int templeft = left, tempright = right - ;
while (templeft < tempright)
{
if (s.charAt(templeft) != s.charAt(tempright)) break;
templeft++; tempright--;
if (templeft >= tempright) return true;
}
//remove left
left++;
while (left < right)
{
if (s.charAt(left) != s.charAt(right)) return false;
left++; right--;
}
}
}
return true;
}
}
参考@yashar 的代码。
解法二：
class Solution {
public boolean validPalindrome(String s)
{
return validPalindrome(s, , s.length() - , false);
}
private boolean validPalindrome(String s, int left, int right, Boolean mismatch)
{
if (right < left) return true;
if (s.charAt(left) != s.charAt(right))
{
if (mismatch == true)
return false;
return validPalindrome(s, left, right - , true) || validPalindrome(s, left + , right, true);
}
else
{
return validPalindrome(s, left + , right - , mismatch);
}
}
}
递归，参考@yashar 的代码。
解法三：
class Solution {
public:
bool validPalindrome(string s) {
return valid(s, , s.length() - , );
}
private:
bool valid(string& s, int i, int j, int d) { // d: num of chars you can delete at most
if (i >= j) return true;
if (s[i] == s[j])
return valid(s, i + , j - , d);
else
return d > && (valid(s, i + , j, d - ) || valid(s, i, j - , d - ));
}
};
递归，参考@alexander 的代码。
最新文章
- Opera放弃自家内核转投WebKit的背后（转）
- [转] - linux下socket编程实例
- HDU 1702 队列与栈的简单运用http://acm.hdu.edu.cn/showproblem.php?pid=1702
- 【js】IE、FF、Chrome浏览器中的JS差异介绍
- G - Oil Skimming - hdu 4185（二分图匹配）
- Linux内核源代码
- 移动端touch触屏滑动事件、滑动触屏事件监听！
- C#对话框的使用
- 查看jar包的jdk版本
- h5属性直接控制上传文件类型
- 高维数据的高速近期邻算法FLANN
- mysql内外连接
- POJ 1185 炮兵阵地 （状态压缩DP）
- Appium+python自动化21-DesiredCapabilities详解
- Windows下Hadoop编程环境配置指南
- mspdb100.dll不见了的解决办法
- django之上传文件和图片
- Elasticsearch Java API深入详解
- Java日志:集成slf4j和logback
- ae（ArcEngine） java swing开发入门系列（1）：开发环境和代码部署