Check Symmetry in Post Titles - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)

U-nderstand

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

• Q: What does it mean for a title to be symmetrical?
  • A: A title is symmetrical if it reads the same forwards and backwards when ignoring spaces, punctuation, and case.
• Q: What should be ignored when checking for symmetry?
  • A: Spaces, punctuation, and case should be ignored.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to compare characters from the beginning and end of the title while skipping non-alphanumeric characters and ignoring case.

1. Initialize two pointers, `left` at the start of the title and `right` at the end.
2. While `left` is less than `right`:
   1. Move `left` pointer to the right if the current character is not alphanumeric.
   2. Move `right` pointer to the left if the current character is not alphanumeric.
   3. Compare the characters at `left` and `right` (convert both to lowercase):
      1. If they don't match, return `False`.
      2. If they do match, move both pointers towards the center.
3. If all characters match, return `True`.

⚠️ Common Mistakes

• Forgetting to skip non-alphanumeric characters.
• Not converting characters to lowercase before comparison.
• Not handling edge cases where the title is empty or contains only non-alphanumeric characters.

I-mplement

def is_symmetrical_title(title):
  left, right = 0, len(title) - 1

  while left < right:
    # Skip non-alphanumeric characters from the left
    while left < right and not title[left].isalnum():
      left += 1

    # Skip non-alphanumeric characters from the right
    while left < right and not title[right].isalnum():
      right -= 1

    # Compare characters (case-insensitive)
    if title[left].lower() != title[right].lower():
      return False

    left += 1
    right -= 1

  return True