Two solutions (optimized and recursive) Java and C#


  • 1

    Java:

    Optimized (Accepted):

    public boolean validPalindrome(String s)
    {
        int left = 0, right = s.length() - 1;
    
        while (left < right)
        {
            if (s.charAt(left) == s.charAt(right))
            {
                left++; right--;
            }
            else
            {
                //remove right
                int templeft = left, tempright = right - 1;
    
                while (templeft < tempright)
                {
                    if (s.charAt(templeft) != s.charAt(tempright)) break;
                    templeft++; tempright--;
    
                    if (templeft >= tempright) return true;
                }
    
                //remove left
                left++;
    
                while (left < right)
                {
                    if (s.charAt(left) != s.charAt(right)) return false;
                    left++; right--;
                }
            }
        }
        return true;
    }
    

    Brute Force (Recursive) (Time Limit Exceeded):

    public boolean validPalindrome(String s) 
    {
        return validPalindrome(s, 0, s.length() - 1, false);
    }
    private boolean validPalindrome(String s, int left, int right, Boolean mismatch)
    {
        if (right - left <= 1) return true;
    
        if (s.charAt(left) != s.charAt(right))
        {
            if (mismatch == true)
                return false;
    
            return validPalindrome(s, left, right - 1, true) || validPalindrome(s, left + 1, right, true);
        }
        else
        {
            return validPalindrome(s, left + 1, right - 1, mismatch);
        }
    }
    

    C#:

    Optimized (Accepted):

    public bool ValidPalindrome(string s)
    {
        int left = 0, right = s.Length - 1;
    
        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++; right--;
            }
            else
            {
                //remove right
                int templeft = left, tempright = right - 1;
    
                while (templeft < tempright)
                {
                    if (s[templeft] != s[tempright]) break;
                    templeft++; tempright--;
    
                    if (templeft >= tempright) return true;
                }
    
                //remove left
                left++;
    
                while (left < right)
                {
                    if (s[left] != s[right]) return false;
                    left++; right--;
                }
            }
        }
        return true;
    }
    

    Brute Force (Recursive) (Time Limit Exceeded):

    public bool ValidPalindrome(string s) //brute force
    {
        return ValidPalindrome(s, 0, s.Length - 1, false);
    }
    private bool ValidPalindrome(string s, int left, int right, bool mismatch)
    {
        if (right - left <= 1) return true;
    
        if (s[left] != s[right])
        {
            if (mismatch == true)
                return false;
    
            return ValidPalindrome(s, left, right - 1, true) || ValidPalindrome(s, left + 1, right, true);
        }
        else
        {
            return ValidPalindrome(s, left + 1, right - 1, mismatch);
        }
    }
    

Log in to reply
 

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