题目:
- 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.
分析:
给定一个非空字符串, 在最多删去一个字符的前提下, 判断是不是回文字符串.
由于删去一个字符也算是回文字符串, 也就说以删去的字符为基础剩下的字符也同样应该是回文字符串. 在这里我们以 abcbda 为例.
从前后开始比较字符是否相同, 当发现 b 和 d 不同时, 我们要删除一个字符, 来继续判断剩下的字符串是否是回文字符串, 因为字符不同, 前后两个都可以删除, 所以返回的两个结果取并集. 删除 b 的话, 显然 cbd 不构成回文字符串, 而删除 d 的话 bcb 构成回文字符串.
程序:
- C++
- class Solution {
- public:
- bool validPalindrome(string s) {
- int l = 0;
- int r = s.size()-1;
- while(l < r){
- if(s[l] != s[r]){
- return isPalindrome(s, l+1, r) || isPalindrome(s, l, r-1);
- }
- else{
- r--;
- l++;
- }
- }
- return true;
- }
- private:
- bool isPalindrome(string s, int l, int r){
- while(l < r){
- if(s[l++] != s[r--])
- return false;
- }
- return true;
- }
- };
- Java
- class Solution {
- public boolean validPalindrome(String s) {
- int l = 0;
- int r = s.length()-1;
- while(l < r){
- if(s.charAt(l) != s.charAt(r))
- return isPalindrome(s, l+1, r) || isPalindrome(s, l, r-1);
- l++;
- r--;
- }
- return true;
- }
- private boolean isPalindrome(String s, int l, int r){
- while(l < r){
- if(s.charAt(l++) != s.charAt(r--))
- return false;
- }
- return true;
- }
- }
来源: http://www.bubuko.com/infodetail-3415312.html