[LeetCode] Valid Palindrome II 验证回文字符串之二
LeetCode 字符串 验证 II 回文 之二 valid Palindrome
2023-09-11 14:21:37 时间
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 = 0, right = s.size() - 1; while (left < right) { if (s[left] != s[right]) return isValid(s, left, right - 1) || isValid(s, left + 1, 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 = 0, right = s.size() - 1; while (left < right) { if (s[left] == s[right]) { ++left; --right; } else { int l = left, r = right - 1; 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: Range Addition
- Leetcode: Logger Rate Limiter
- Leetcode: Maximum XOR of Two Numbers in an Array
- Leetcode: Perfect Rectangle
- Leetcode: Unique Binary Search Trees
- 180、【动态规划】leetcode ——583. 两个字符串的删除操作:两种动态规划思路(C++版本)
- 【数据结构/字符串】leetcode刷题路线(持续更新)
- LeetCode 06 ZigZag Conversion
- leetcode——Reverse Words in a String 旋转字符串中单词顺序(AC)
- [LeetCode] 1047. Remove All Adjacent Duplicates In String 移除字符串中所有相邻的重复字符
- [LeetCode] 993. Cousins in Binary Tree 二叉树的表兄弟节点
- [LeetCode] Find And Replace in String 在字符串中查找和替换
- [LeetCode] Custom Sort String 自定义排序的字符串
- [LeetCode] Minimum ASCII Delete Sum for Two Strings 两个字符串的最小ASCII删除和
- [LeetCode] Count Binary Substrings 统计二进制子字符串
- [LeetCode] Bulb Switcher II 灯泡开关之二
- [LeetCode] Construct String from Binary Tree 根据二叉树创建字符串
- [LeetCode] 598. Range Addition II 范围相加之二
- [LeetCode] 248. Strobogrammatic Number III 对称数之三
- [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二
- [LeetCode] 8. String to Integer (atoi) 字符串转为整数
- leetcode 530. Minimum Absolute Difference in BST二叉搜索树的最小绝对差 (简单)