Click here to see the full article post
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, Non-decreasing 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 non-decreasing. 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 = S[len(S) - 1], then it could still be the case that removing
S[len(S) - 1] results in a palindrome too, but these choices are weakly dominated by solving on
(S, ..., 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.
I see. I took it for granted that we should skip all the front-back pairs of equal character, and thought the story only began at the first unequal pair. Now I can see your solution does have the Greedy component in it. Thanks.
The solution for the second approach is really poorly worded. This link explains the methodology better:
@david301 When checking
is_pali_range(i, j), we wanted to know if all
s[i] == s[j],
s[i+1] == s[j-1], etc. are true. More generally, this is
s[i+d] == s[j-d].
k ranges from
k = i+d. Then
j-d = j + i - k. So we want
s[k] == s[j+i-k].
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.