Two Pointer Palindrome - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Strings, Two-Pointer Technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is a string s containing only lowercase alphabetic characters.

• Q: What is the expected output of the function?

  • A: The function should return True if the string s is a palindrome, and False otherwise.

• Q: What is a palindrome?

  • A: A palindrome is a string that reads the same forward and backward. For example, "radar" is a palindrome.

• Q: What should the function return if the string is empty?

  • A: An empty string is considered a palindrome, so the function should return True.

• Q: Are there any constraints on the input?

  • A: The string contains only lowercase alphabetic characters, and there are no spaces or special characters.

• The function is_palindrome() should check if a given string reads the same backward as forward. Only lowercase alphabetic characters are considered.

HAPPY CASE
Input: "madam"
Expected Output: True

UNHAPPY CASE
Input: "madamweb"
Expected Output: False

EDGE CASE
Input: "
Expected Output: True

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to compare characters from both ends of the string and move towards the center.

1. Initialize two pointers: one at the beginning (left) and one at the end (right) of the string.
2. While the left pointer is less than the right pointer:
   a. If the characters at both pointers do not match, return False.
   b. Move the left pointer one step to the right and the right pointer one step to the left.
3. If all characters match, return True.

⚠️ Common Mistakes

• Forgetting to check both pointers before accessing the string.
• Not handling edge cases, such as empty strings.

I-mplement

Implement the code to solve the algorithm.

def is_palindrome(s):
    # Initialize two pointers
    left = 0
    right = len(s) - 1
    
    # Move the pointers towards each other
    while left < right:
        # If the characters at the pointers don't match, it's not a palindrome
        if s[left] != s[right]:
            return False
        # Move the pointers
        left += 1
        right -= 1
    
    # If all characters matched, it's a palindrome
    return True