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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.