bonus07Logic.md

Code Recap:

class Solution {
     public boolean sentencePalindrome(String s) {
        // Step 1: Process the string to remove non-alphanumeric characters and convert to lowercase
        StringBuilder processedString = new StringBuilder();
        
        // Traverse the input string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If the character is alphanumeric, add it to the processed string in lowercase
            if (Character.isLetterOrDigit(c)) {
                processedString.append(Character.toLowerCase(c));
            }
        }

        // Step 2: Check if the processed string is a palindrome
        int left = 0;
        int right = processedString.length() - 1;
        
        while (left < right) {
            if (processedString.charAt(left) != processedString.charAt(right)) {
                return false; // Return false if characters don't match
            }
            left++;
            right--;
        }

        return true; // Return true if it's a palindrome
    }
}

Dry Run

Let's dry run the sentencePalindrome method using the input:

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

Step 1: Process the String

We start by removing non-alphanumeric characters and converting the string to lowercase. The characters that remain are:

1. Start with an empty processedString: ""

2. Traverse the string character by character:

   • 'A' → Add 'a' to processedString → "a"
   • ' ' → Skip (non-alphanumeric)
   • 'm' → Add 'm' to processedString → "am"
   • 'a' → Add 'a' to processedString → "ama"
   • 'n' → Add 'n' to processedString → "aman"
   • Continue this process for the whole string...

   After processing, the processedString becomes:

   "amanaplanacanalpanama"
   

Step 2: Check if the String is a Palindrome

Now we compare the string to check if it reads the same forwards and backwards.

1. Initialize left = 0 and right = processedString.length() - 1 = 20.

2. Compare characters at left and right:

   • processedString.charAt(0) ('a') == processedString.charAt(20) ('a')
   • processedString.charAt(1) ('m') == processedString.charAt(19) ('m')
   • Continue comparing characters inwards...

   After several comparisons, we find that all characters match, and we reach the center of the string with left = 10 and right = 10.

Conclusion:

Since all character pairs match, the string is a palindrome. Therefore, the method will return true.

Time Complexity:

• String Processing: O(n), where n is the length of the input string.
• Palindrome Check: O(n), where n is the length of the processed string.
• Total Time Complexity: O(n)

Space Complexity:

• Processed String: O(n), where n is the length of the input string.
• Total Space Complexity: O(n)