# Solution by rohitnandi12

• 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 :)**

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