Find First Symmetrical Landmark Name - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 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 is the input to the problem?
  • A: The input is an array of strings landmarks, where each string represents the name of a landmark.
• Q: What is the output?
  • A: The output is the first landmark name in the array that is symmetrical (i.e., reads the same forward and backward). If no such name exists, return an empty string ".
• Q: How is a landmark name determined to be symmetrical?
  • A: A landmark name is considered symmetrical if it reads the same forward and backward, which means it is a palindrome.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the array of landmark names and check each one to see if it is a palindrome. Return the first palindrome found, or return an empty string if no palindrome exists.

1. Define a helper function `is_palindrome(landmark)` that checks whether a given string is a palindrome:
   1. Initialize two pointers, `left` at the start of the string and `right` at the end.
   2. While `left` is less than `right`, compare the characters at these positions:
      * If the characters are different, return `False`.
      * If the characters are the same, move `left` one step to the right and `right` one step to the left.
   3. If all characters match, return `True`.
2. Iterate through the `landmarks` array:
   1. For each landmark, use `is_palindrome` to check if it is a palindrome.
   2. If a palindrome is found, return that landmark.
3. If no palindrome is found after iterating through all landmarks, return an empty string `"`.

⚠️ Common Mistakes

• Forgetting to handle the case where no palindrome exists in the list, leading to incorrect results.
• Incorrectly implementing the palindrome check, such as not properly updating the pointers or comparing characters.
• Not considering edge cases, such as very short or empty landmark names.

I-mplement

def is_palindrome(landmark):
    left, right = 0, len(landmark) - 1
    while left < right:
        if landmark[left] != landmark[right]:
            return False
        left += 1
        right -= 1
    return True

def first_symmetrical_landmark(landmarks):
    for landmark in landmarks:
        if is_palindrome(landmark):
            return landmark
    return ""

# Example usage
print(first_symmetrical_landmark(["canyon","forest","rotor","mountain"]))  # Output: "rotor"
print(first_symmetrical_landmark(["plateau","valley","cliff"]))            # Output: ""