Valid Palindrome II


  • 0

    Click here to see the full article post


  • 1
    K

    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.


  • 0

    @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 removing S[0] or S[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.


  • 0
    K

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.