NUHMAN.com

Introduction

The problem LeetCode 246: Strobogrammatic Number asks us to determine whether a given number is strobogrammatic. A number is strobogrammatic if it appears the same when rotated 180 degrees (i.e., turned upside down). This is a common type of problem in coding interviews that tests string manipulation and mapping.

Let’s break this problem down and solve it step-by-step using Python.

Problem Statement

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

Example:

vbnet

Input: num = "69"
Output: true

Input: num = "88"
Output: true

Input: num = "962"
Output: false

Step-by-Step Solution in Python

Step 1: Understand Valid Digits

We must understand which digits look like themselves or transform into another valid digit when rotated 180 degrees:

• '0' → '0'
• '1' → '1'
• '6' → '9'
• '8' → '8'
• '9' → '6'

Any other digit (like 2, 3, 4, 5, 7) is invalid because it doesn't appear valid upside down.

Step 2: Use Two Pointers

Use a two-pointer approach starting from the beginning and end of the string:

• For each pair of digits (left and right), check whether they map to each other using a dictionary.

Step 3: Code It

python

def isStrobogrammatic(num: str) -> bool:
    # Mapping of digits to their 180-degree rotated equivalents
    mapping = {
        '0': '0',
        '1': '1',
        '6': '9',
        '8': '8',
        '9': '6'
    }

    left, right = 0, len(num) - 1

    while left <= right:
        left_digit = num[left]
        right_digit = num[right]

        # Check if left_digit has a valid mapping
        if left_digit not in mapping:
            return False
        
        # Check if the mapped left_digit equals the right_digit
        if mapping[left_digit] != right_digit:
            return False

        left += 1
        right -= 1

    return True

Explanation of the Code

1. Mapping Setup:
2. Create a dictionary that maps each digit to its corresponding upside-down version.
3. Pointer Initialization:
4. Use left and right pointers to compare digits from both ends.
5. Validation:

• If the current digit doesn’t exist in the mapping, it’s invalid.
• If the mapped value doesn’t match the digit on the opposite end, return False.

1. Continue:
2. Move the pointers inward and repeat the check.
3. Return True:
4. If all checks pass, return True.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string. We traverse the string once.
• Space Complexity: O(1), as the mapping dictionary is constant in size.

Conclusion

This problem is a great example of string manipulation and using dictionaries effectively. It also highlights a clean two-pointer strategy. Practicing problems like these can significantly boost your confidence in technical interviews.