Palindromic Name - codepath/compsci_guides GitHub Wiki

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

Problem 4: Palindromic Name

Queen Ada is superstitious and believes her children will only have good fortune if their name is symmetrical and reads the same forward and backward. Write a recursive function that takes in a string comprised of only lowercase alphabetic characters name and returns True if the name is palindromic and False otherwise.

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Recursion, String Manipulation

1: U-nderstand

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

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to check if a given name is a palindrome using a recursive function.
  • Q: Can the string be empty?
    • A: Yes, an empty string should be considered a palindrome.
HAPPY CASE
Input: "eve"
Output: True
Explanation: The string "eve" reads the same forward and backward, so it is a palindrome.

Input: "ling"
Output: False
Explanation: The string "ling" does not read the same forward and backward, so it is not a palindrome.

EDGE CASE
Input: "
Output: True
Explanation: An empty string is considered a palindrome by definition.

Input: "a"
Output: True
Explanation: A single character string is always a palindrome.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Palindrome Checking, we want to consider the following approaches:

  • Recursive Comparison: Recursively compare the first and last characters of the string. If they match, check the substring excluding these characters.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • A palindrome reads the same forward and backward. To check this recursively, compare the first and last characters and then recursively check the middle portion of the string.

Recursive Approach:

1) Base case 1: If the string `name` is empty or has one character, return True (since it's a palindrome).
2) Base case 2: If the first and last characters of `name` don't match, return False.
3) Recursive case: Return the result of the function called on the substring `name[1:-1]` (excluding the first and last characters).

⚠️ Common Mistakes

  • Not correctly identifying the base cases, which can lead to incorrect results or infinite recursion.
  • Incorrectly handling the indices or slicing of the string, leading to off-by-one errors.

4: I-mplement

Implement the code to solve the algorithm.

def is_palindrome(name):
    # Base case 1: An empty string or a single character string is a palindrome
    if len(name) <= 1:
        return True
    
    # Base case 2: If the first and last characters don't match, it's not a palindrome
    if name[0] != name[-1]:
        return False
    
    # Recursive case: Check the substring excluding the first and last characters
    return is_palindrome(name[1:-1])

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the is_palindrome function with the input "eve". The function should return True after comparing the first and last characters and recursively checking the middle portion.
  • Test the function with edge cases like an empty string ". The function should return True, correctly identifying the base case.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(N) where N is the length of the string. The function processes each character at most once.
  • Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the length of the string.