Problem-Solving Guide for Beginners
Problem Statement
Determine if a given string reads the same forwards and backwards. Ignore spaces and case.
Example Inputs
JavaScript Method - Using Only String Methods
Approach
To check if a string is a palindrome, we can convert the string to lowercase, remove spaces, and then check if it reads the same forwards and backwards. A simple approach is to compare the cleaned string with its reverse.
Steps
- Convert the string to lowercase using
.toLowerCase().
- Remove spaces using
.replace(/\s+/g, '').
- Reverse the cleaned string using
split('').reverse().join('').
- Check if the cleaned string is equal to its reversed version.
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the string, as we traverse the string a limited number of times.
- Space Complexity: O(n), since a new string is created to store the reversed version.
Code Snippet
Dry Run
Example input: "Racecar"
- Step 1:
str.toLowerCase() → "racecar"
- Step 2:
"racecar".replace(/\s+/g, '') → "racecar"
- Step 3:
"racecar".split('').reverse().join('') → "racecar"
- Step 4: Check if
"racecar" === "racecar" → true
Alternative Approach - Without Using JavaScript String Methods
Approach
We can use a two-pointer technique to check if a string is a palindrome without using built-in string methods. By ignoring spaces and case, we can compare characters from the beginning and end of the string until they meet in the middle.
Steps
- Initialize two pointers:
left at the beginning of the string and right at the end.
- Ignore spaces and convert characters to lowercase while moving the pointers.
- Compare the characters at
left and right. If they differ, return false.
- If they are the same, move the pointers inward and continue.
- If all pairs match, return
true.
Time & Space Complexity
- Time Complexity: O(n), as we traverse each character at most once.
- Space Complexity: O(1), as no extra space is needed beyond the pointers.
Code Snippet
Dry Run
Example input: "Racecar"
- Initial state:
left = 0, right = 6
- Characters compared:
str[left] = 'r', str[right] = 'r' → Match- Move pointers inward:
left = 1, right = 5
str[left] = 'a', str[right] = 'a' → Match- Continue until
left >= right
- Final output:
true
Complexity Analysis
JavaScript Method (Using String Methods)
- Time Complexity: O(n)
- Space Complexity: O(n)
Alternative Approach (Without String Methods)
- Time Complexity: O(n)
- Space Complexity: O(1)
Conclusion
To check if a string is a palindrome, we can either use JavaScript string methods for simplicity or a two-pointer approach for efficiency. Both approaches provide similar time complexity, but the two-pointer approach has a space advantage.