Solution by rohitnandi12


  • 0
    R

    Primary Thoughts

    What is a Palindrome?

    A word, phrase, or sequence that reads the same backwards as forwards, e.g. "madam" or "nurses run"

    Fastest way to check a string is Palindrome or not?

    Two Pointer Method : Take two pointer, Start and End. Traverse the string, at any point of time i, Start and End will represent the ith string from beginning and end respectively.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    T1 : "A man, a plan, a canal: Panama" // true
    T2 : "race a car"                     // false
    T3 : ""                               // true
    T4 : ",,,,,,,a"                       // true
    T4 : ",,,,,,,"                        // true
    
    

    Approach #1

    Intuition
    Remove all the characters other than a digit or a letter and then use Two pointer method. The downfall is removing all the unwanted characters and reforming the string is costly depending on the approach you choose. We can do better than this and in O(n) time. Yeah guys, you heard that right. :-D


    Approach #2 Modified Two Pointer Algorithm [Accepted]

    Algorithm

    • Initialize two pointer start which points to front and end which points to last character
    • Loop while start is less than end
      • If start does not point to a letter or digit, keep moving forward
      • If end does not point to a letter or digit, keep moving backward
      • check if the characters pointed by start and end are same or not, If not break
        else go to next iteration
    • return true if start is greater or equal to end, else false

    Java

    class Solution {
        public boolean isPalindrome(String s) {
    
            if(s.length()<2)return true;
            
            s = s.toLowerCase();
            int start=0,end=s.length()-1;
            
            while(start<end){
                
                char first = s.charAt(start);
                while(start<end && isNotLetterDigit(first)){
                    first = s.charAt(++start);
                }
                
                char last = s.charAt(end);
                while(start<end && isNotLetterDigit(last)){
                    last = s.charAt(--end);
                }
                
                if(first!=last)break;
                ++start;
                --end;
            }
            
            return start>=end;
        }
        private boolean isNotLetterDigit(char c){
            return !((c>='0' && c<='9') || (c>='a' && c<='z'));
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$

    • Space complexity : $$O(1)$$

    ** Thank You.. Happy Coding :)**


Log in to reply
 

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