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


  • 1
    class Solution(object):
        def validPalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            l, r = 0, len(s)-1
            while l < r:
                if s[l] == s[r]:
                    l += 1
                    r -= 1
                else:
                    tmp1 = s[:l]+s[l+1:]
                    tmp2 = s[:r]+s[r+1:]
                    return tmp1 == tmp1[::-1] or tmp2 == tmp2[::-1]:
            return True
    

  • 0
    J

    May I ask if the question requires adding one character to anywhere in a string, how to check whether the original string can be changed to a palindrome?


  • 0
    H

    Easy to understand solution :)

    class Solution {
    public:
    bool validPalindrome(string s) {

        int len = s.length();
        int back = len-1;
        
        string temp1 = s, temp2 = s;
        bool flag = false;
        
        for(int front=0;front<len/2;front++){
            if(s[front] != s[back-front]){
                temp1.erase(front,1);
                temp2.erase(back-front,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;
    }
    

    };


  • 0

    This is my really easy and well-commented solution without a helper function.


  • 0
    C

    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;
    }

Log in to reply
 

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