680. 验证回文字符串 Ⅱ

转载自Leet Code

题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1: >输入: "aba" >输出: True

示例 2: >输入: "abca" >输出: True >解释: 你可以删除c字符。

注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

---

我的代码

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}

class MySolution680 
{
    public boolean validPalindrome(String s) 
    {
    	int head=0, tail=s.length()-1;
    	
    	for (; head<tail; head++,tail--)
    	{
    		if (s.charAt(head)!=s.charAt(tail)) break;
    	}
    	if (head>=tail) return true;
    	
    	int newHead = head+1; int newTail = tail;
    	for (; newHead<newTail; newHead++, newTail--)
    	{
    		if (s.charAt(newHead)!=s.charAt(newTail)) break;
    	}
    	if (newHead>=newTail) return true;
    	
    	newHead = head; newTail = tail-1; 
    	for (; newHead<newTail; newHead++, newTail--)
    	{
    		if (s.charAt(newHead)!=s.charAt(newTail)) return false;
    	}
    	return true;
    }
}