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.


  • 0
    T
    This post is deleted!

  • 0
    S

    The solution for the second approach is really poorly worded. This link explains the methodology better:
    http://www.geeksforgeeks.org/remove-character-string-make-palindrome/


  • 0
    D

    I don't understand the indexes. What does (j - k + i) do?


  • 0

    @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].

    So, as k ranges from i to j, put k = i+d. Then j-d = j + i - k. So we want s[k] == s[j+i-k].


Log in to reply
 

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