🚀Day 16/180 125. Valid Palindrome || (Leetcode) 125. Valid Palindrome

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

class Solution {
    // This function compares the first and last characters of the string
    private boolean checkPalindrome(int i, char[] ch, int n) {
        if (i >= n / 2) // if the string is a palindrome, we only need to check up to half its length
            return true;

        if (ch[i] != ch[n - i - 1]) // if any character does not match its counterpart, return false
            return false;

        return checkPalindrome(i + 1, ch, n); // call the function for i + 1
    }

    public boolean isPalindrome(String s) {
        List<Character> chList = new ArrayList<>(); // To store the characters of the string

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLowerCase(c) || Character.isDigit(c)) {
                chList.add(c); // Store the character in chList
            } else if (Character.isUpperCase(c)) {
                char lower = Character.toLowerCase(c); // Convert uppercase letter to lowercase
                chList.add(lower); // Store the character in chList
            }
        }

        int len = chList.size(); // This will store the size of chList, which will be used in the checkPalindrome function
        char[] ch = new char[len];
        for (int i = 0; i < len; i++) {
            ch[i] = chList.get(i);
        }

        return checkPalindrome(0, ch, len); // If the function returns true, the string is a palindrome; otherwise, it's not
    }
}

Let's dry run the provided Java code with an example input string "A man, a plan, a canal: Panama".

Dry Run:

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

1. Initial Setup:

   • s = "A man, a plan, a canal: Panama"

2. Preprocessing:

   • Initialize chList to store the characters after filtering and conversion.

   • Loop through each character in the string:

     • 'A' (uppercase) -> converted to 'a' -> added to chList.

     • ' ' (space) -> ignored.

     • 'm' -> added to chList.

     • 'a' -> added to chList.

     • 'n' -> added to chList.

     • ' ' (space) -> ignored.

     • 'a' -> added to chList.

     • ' ' (space) -> ignored.

     • 'p' -> added to chList.

     • 'l' -> added to chList.

     • 'a' -> added to chList.

     • 'n' -> added to chList.

     • ' ' (space) -> ignored.

     • 'a' -> added to chList.

     • ' ' (space) -> ignored.

     • 'c' -> added to chList.

     • 'a' -> added to chList.

     • 'n' -> added to chList.

     • 'a' -> added to chList.

     • 'l' -> added to chList.

     • ':' (colon) -> ignored.

     • ' ' (space) -> ignored.

     • 'P' (uppercase) -> converted to 'p' -> added to chList.

     • 'a' -> added to chList.

     • 'n' -> added to chList.

     • 'a' -> added to chList.

     • 'm' -> added to chList.

     • 'a' -> added to chList.

3. Convert chList to ch array:

   • chList = [a, m, a, n, a, p, l, a, n, a, c, a, n, a, l, a, p, a, n, a, m, a]

   • Convert chList to char[] ch.

4. Checking Palindrome:

   • Call checkPalindrome(0, ch, len) where len = 21.

5. Recursive Calls:

   • checkPalindrome(0, ch, 21): Compare ch[0] with ch[20] ('a' == 'a'), proceed.

   • checkPalindrome(1, ch, 21): Compare ch[1] with ch[19] ('m' == 'm'), proceed.

   • checkPalindrome(2, ch, 21): Compare ch[2] with ch[18] ('a' == 'a'), proceed.

   • checkPalindrome(3, ch, 21): Compare ch[3] with ch[17] ('n' == 'n'), proceed.

   • checkPalindrome(4, ch, 21): Compare ch[4] with ch[16] ('a' == 'a'), proceed.

   • checkPalindrome(5, ch, 21): Compare ch[5] with ch[15] ('p' == 'p'), proceed.

   • checkPalindrome(6, ch, 21): Compare ch[6] with ch[14] ('l' == 'l'), proceed.

   • checkPalindrome(7, ch, 21): Compare ch[7] with ch[13] ('a' == 'a'), proceed.

   • checkPalindrome(8, ch, 21): Compare ch[8] with ch[12] ('n' == 'n'), proceed.

   • checkPalindrome(9, ch, 21): Compare ch[9] with ch[11] ('a' == 'a'), proceed.

   • checkPalindrome(10, ch, 21): (Base case) i >= n/2, return true.

Since all recursive calls return true, the final result is true.

Conclusion:

The input string "A man, a plan, a canal: Panama" is a palindrome, as confirmed by the dry run.