leetcode 340，leetcode-680-Valid Palindrome II

題目描述：

Given a non-empty string?s, you may delete?at most?one character. Judge whether you can make it a palindrome.

leetcode 340？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.

?

要完成的函數：

bool validPalindrome(string s)?

?

說明：

1、給定一個字符串，至多刪去里面的一個字符，使其成為一個回文串。判斷能不能實現。

2、我們先看一個例子

abca

acba（反轉）

我們可以看到第一個字母是一樣的，第二個字母的時候就對不上了，那我們如果要形成一個回文串，可以試著刪去第二個字母b，也可以刪去從后面數起第二個字母c，只要之后能一一對上，那么還是一個回文串。

?

關于這兩種情況，給兩個例子來說明一下：

ececabbacec，這個字符串，我們看到第一個字符e和最后一個字符c沒對上，我們可以刪去e，這樣子能形成回文串。我們也能刪去c，但這樣形成不了回文串。這是要刪去前面字符的例子。

abbca，這個字符串，如果刪去前面字符b，那么形成不了回文串，如果刪去后面字符c，剛好能形成回文串。這是要刪去后面字符的例子。

?

所以我們要分成兩種情況來判斷處理。

按照上述邏輯來處理一下，構造如下代碼：（附解釋）

    bool validPalindrome(string s) {int i=0,j=s.size()-1;while(i<j){if(s[i]!=s[j])//當碰到對不上的時候，記錄i和j的值break;i++;j--; }int i1=i,j1=j;//記錄一個副本i++;//如果刪去前面的字符，i++，處理下一個bool flag=1;while(i<j){if(s[i]!=s[j])//如果出現第二次對不上的情況{flag=0;break;}i++;j--;}if(flag==1)//如果全程都對得上，那么返回truereturn true;j1--;//如果刪去前面的字符對不上了，那么刪去后面的字符試試while(i1<j1){if(s[i1]!=s[j1])//如果還是對不上，返回falsereturn false;i1++;j1--;}return true;//如果全程對得上，那么返回true}

上述代碼實測119ms，beats 90.33% of cpp submissions。