🚀Day 22/180 125. Valid Palindrome (LeetCode)

125. Valid Palindrome

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

class Solution {
    public static boolean recursive(String s,int start,int end){
        //char ch =;
        char startCh=s.charAt(start);
        char endCh=s.charAt(end);
        if(start>=end){
            return true;
        }
        if(!(Character.isLetterOrDigit(startCh))){
            return recursive(s,start+1,end);
        }
        if(!(Character.isLetterOrDigit(endCh))){
            return recursive(s,start,end-1);
        }
        if (Character.toLowerCase(startCh) != Character.toLowerCase(endCh)) {  
                return false; // Not a palindrome  
            }
        return recursive(s,start+1,end-1); 
    }
    public boolean isPalindrome(String s) {
        int n= s.length();
        int start =0;
        int end = n-1;
        return recursive(s,start,end);
    }
}

DRY RUN :

Let's dry run the code step-by-step with an example string "A man, a plan, a canal: Panama".

Initial Setup

• Input String: "A man, a plan, a canal: Panama"

• Start Index (start): 0

• End Index (end): 29 (length of the string - 1)

Iteration 1

• start: 0, end: 29

• startCh: 'A' (s.charAt(0))

• endCh: 'a' (s.charAt(29))

• Both are alphanumeric and Character.toLowerCase('A') == Character.toLowerCase('a')

• start incremented to 1, end decremented to 28

Iteration 2

• start: 1, end: 28

• startCh: ' ' (space, s.charAt(1))

• Not alphanumeric, start incremented to 2

Iteration 3

• start: 2, end: 28

• startCh: 'm' (s.charAt(2))

• endCh: 'm' (s.charAt(28))

• Both are alphanumeric and Character.toLowerCase('m') == Character.toLowerCase('m')

• start incremented to 3, end decremented to 27

Iteration 4

• start: 3, end: 27

• startCh: 'a' (s.charAt(3))

• endCh: 'a' (s.charAt(27))

• Both are alphanumeric and Character.toLowerCase('a') == Character.toLowerCase('a')

• start incremented to 4, end decremented to 26

Iteration 5

• start: 4, end: 26

• startCh: 'n' (s.charAt(4))

• endCh: 'n' (s.charAt(26))

• Both are alphanumeric and Character.toLowerCase('n') == Character.toLowerCase('n')

• start incremented to 5, end decremented to 25

Iteration 6

• start: 5, end: 25

• startCh: ',' (comma, s.charAt(5))

• Not alphanumeric, start incremented to 6

Iteration 7

• start: 6, end: 25

• startCh: ' ' (space, s.charAt(6))

• Not alphanumeric, start incremented to 7

Iteration 8

• start: 7, end: 25

• startCh: 'a' (s.charAt(7))

• endCh: 'a' (s.charAt(25))

• Both are alphanumeric and Character.toLowerCase('a') == Character.toLowerCase('a')

• start incremented to 8, end decremented to 24

This process continues, skipping non-alphanumeric characters and comparing alphanumeric ones in a similar manner.

Final Iterations

• start: 13, end: 16

• startCh: 'p' (s.charAt(13))

• endCh: 'P' (s.charAt(16))

• Both are alphanumeric and Character.toLowerCase('p') == Character.toLowerCase('P')

• start incremented to 14, end decremented to 15

• start: 14, end: 15

• startCh: 'l' (s.charAt(14))

• endCh: 'l' (s.charAt(15))

• Both are alphanumeric and Character.toLowerCase('l') == Character.toLowerCase('l')

• start incremented to 15, end decremented to 14

At this point, start (15) is no longer less than end (14), so the while loop terminates and the method returns true.

The string "A man, a plan, a canal: Panama" is a palindrome as expected.