Valid Palindrome II


Can you please explain why you think the second approach is Greedy? My understanding about Greedy is that you must figure out a correct way to decide which character to remove, rather than trying both ways and check out which way works.
For example, Problem 665, Nondecreasing array, is similar to this one. In Problem 665, there is a greedy approach to decide how to modify an element in the array to make the array nondecreasing. But in this problem, I don't see we have a counterpart.

@kamfung2017 We are faced with the decision of what
S[k]
to remove to check whether the result is a palindrome. When say,S[0] = S[len(S)  1]
, then it could still be the case that removingS[0]
orS[len(S)  1]
results in a palindrome too, but these choices are weakly dominated by solving on(S[1], ..., S[len(S)  2])
.This is what I meant by a "greedy" choice: between local options we chose the one that dominates the other. At the end when we only have to check at most 2 such
k
, I consider this a stopping condition. By all means if you prefer to call it something else, do so. I was just trying to choose a relatively descriptive word for the heading.

The solution for the second approach is really poorly worded. This link explains the methodology better:
http://www.geeksforgeeks.org/removecharacterstringmakepalindrome/

@david301 When checking
is_pali_range(i, j)
, we wanted to know if alls[i] == s[j]
,s[i+1] == s[j1]
, etc. are true. More generally, this iss[i+d] == s[jd]
.So, as
k
ranges fromi
toj
, putk = i+d
. Thenjd = j + i  k
. So we wants[k] == s[j+ik]
.

Easy to understand solution :)
class Solution {
public:
bool validPalindrome(string s) {int len = s.length(); int back = len1; string temp1 = s, temp2 = s; bool flag = false; for(int front=0;front<len/2;front++){ if(s[front] != s[backfront]){ temp1.erase(front,1); temp2.erase(backfront,1); flag = true; break; } } if(flag == true){ string chk1 = temp1, chk2 = temp2; reverse(chk1.begin(),chk1.end()); reverse(chk2.begin(),chk2.end()); if(temp1==chk1 or temp2==chk2) return true; else return false; } return true; }
};


Second Approach :Here is my solution using while loop instead of for loop which makes it easy to deal with index calculation,
public bool ValidPalindrome(string s) {
int start=0; int end = s.Length  1;
while(start< end)
{
if(s[start] != s[end])
return IsPalindrome(s,start+ 1, end) IsPalindrome(s,start, end 1) ;
start++;
end;
}
return true;
}public bool IsPalindrome(string s, int start, int end) { while(start< end) { if(s[start] != s[end]) return false; start++; end; } return true; }