ValidPalindromeII [source code]

public class ValidPalindromeII {
static
/******************************************************************************/
class Solution {
    public boolean validPalindrome(String s) {
        if (s.length () <= 1)
            return true;
        char[] chs = s.toCharArray ();
        int lo = 0, hi = chs.length - 1;
        while (lo <= hi && chs[lo] == chs[hi]) {
            lo++;
            hi--;
        }
        // If all match, then finish
        if (lo > hi)
            return true;
        // LO2 represents the new LO if we skip [LO], and HI2 if we skip [HI]
        int lo2 = lo + 1, hi2 = hi - 1;
        // Will skipping [LO] make things work? 
        while (lo2 <= hi && chs[lo2] == chs[hi]) {
            lo2++;
            hi--;
        }
        if (lo2 > hi)
            return true;
        // Will skipping [HI] make things work?
        while (lo <= hi2 && chs[lo] == chs[hi2]) {
            lo++;
            hi2--;
        }
        if (lo > hi2)
            return true;
        // Doesn't work
        return false;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidPalindromeII.Solution tester = new ValidPalindromeII.Solution();
    }
}

看起来很玄的一个题目, 不过好像稍微有点思路;

本来还以为挺没有思路的一个题目, 最后直接10分钟秒杀, 速度是37ms (85%), 也不难接受;

需要提到的一个点是, 当我看到delete的时候, 脑子里有印象, 以前见过一个点子, 就是add and delete的处理的互换; 当然, 最后发现这个东西在这里并没有用武之地, 不过能想到还是不错的;

这个题目本身并不考察高深的算法, 就是考察一下你有没有具体分析解决这个问题的思维能力;

这个题目能这么快的做完很大程度上得益于立刻就开始了笔算, 然后很快的找到了思路; 快速开始写代码, 在实际写代码的过程当中, 又发现了更多的优化空间;

editorial 2

Intuition

If the beginning and end characters of a string are the same (ie. s[0] == s[s.length - 1]), then whether the inner characters are a palindrome (s[1], s[2], ..., s[s.length - 2]) uniquely determines whether the entire string is a palindrome.

Algorithm

Suppose we want to know whether s[i], s[i+1], ..., s[j] form a palindrome. If i >= j then we are done. If s[i] == s[j] then we may take i++; j--. Otherwise, the palindrome must be either s[i+1], s[i+2], ..., s[j] or s[i], s[i+1], ..., s[j-1], and we should check both cases.

class Solution {  
    public boolean isPalindromeRange(String s, int i, int j) {  
        for (int k = i; k <= i + (j - i) / 2; k++) {  
            if (s.charAt(k) != s.charAt(j - k + i)) return false;  
        }  
        return true;  
    }  
    public boolean validPalindrome(String s) {  
        for (int i = 0; i < s.length() / 2; i++) {  
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {  
                int j = s.length() - 1 - i;  
                return (isPalindromeRange(s, i+1, j) ||  
                        isPalindromeRange(s, i, j-1));  
            }  
        }  
        return true;  
    }  
}

他这个算法用了一个类似recursion的想法, 不过感觉不如我的, 好像做了一点无用功? 不对, 其实是类似的思路;

submission最优解基本也是波动;

Problem Description

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:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Difficulty:Easy
Total Accepted:17.5K
Total Submissions:53.8K
Contributor:今が最高
Companies
facebook
Related Topics
string
Similar Questions
Valid Palindrome