Domain 1EasyCORE

Strobogrammatic Number

The problem asks us to determine if a given string `num`, which represents an integer, is a strobogrammatic number. A strobogrammatic number looks the same when rotated 180 degrees. The input is a string of digits, and the output should be a boolean indicating whether the number is strobogrammatic or not.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Math

246. Strobogrammatic Number

Model: qwen2.5-coder:14b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 46.4%


Problem Breakdown

The problem asks us to determine if a given string num, which represents an integer, is a strobogrammatic number. A strobogrammatic number looks the same when rotated 180 degrees. The input is a string of digits, and the output should be a boolean indicating whether the number is strobogrammatic or not.

Inputs:

  • num: A string representing an integer.

Outputs:

  • A boolean value (true or false) indicating if num is a strobogrammatic number.

Implicit Constraints:

  • The length of num is between 1 and 50.
  • num consists only of digits.
  • num does not contain leading zeros except for the number zero itself.

Tricky Edge Cases:

  • Single-digit numbers (e.g., “1”, “8”).
  • Numbers with an odd length that have a middle digit that is not strobogrammatic (e.g., “962”).
  • Numbers with leading zeros (though the problem constraints prevent this).

Intuition

A brute-force approach would involve checking each digit of the number to see if it can be rotated 180 degrees and matches its counterpart from the other end. However, this approach is inefficient because it requires multiple passes over the string.

The key insight is that we can use a hash table (dictionary) to map each digit to its strobogrammatic counterpart. By iterating through the string from both ends towards the center, we can check if each pair of digits matches according to the mapping. This approach ensures that we only need one pass over the string, making it more efficient.

Approach

  1. Create a dictionary strob_map that maps each strobogrammatic digit to its counterpart.
  2. Initialize two pointers: left at the start of the string and right at the end.
  3. Iterate while left is less than or equal to right:
    • If the character at num[left] is not in strob_map, return false.
    • If the character at num[right] does not match the strobogrammatic counterpart of num[left], return false.
    • Move the left pointer one step to the right and the right pointer one step to the left.
  4. If all pairs match, return true.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string num. We iterate through the string once.
  • Space Complexity: O(1). The space used by the dictionary is constant since it only contains a fixed number of strobogrammatic digit pairs.

Solution

def isStrobogrammatic(num: str) -> bool:
    # Mapping of strobogrammatic digits to their counterparts
    strob_map = {
        '0': '0',
        '1': '1',
        '6': '9',
        '8': '8',
        '9': '6'
    }
    
    left, right = 0, len(num) - 1
    
    while left <= right:
        if num[left] not in strob_map or strob_map[num[left]] != num[right]:
            return False
        left += 1
        right -= 1
    
    return True

Edge Cases Handled

  • Single-digit numbers: The dictionary strob_map includes mappings for “0”, “1”, and “8”, which are strobogrammatic.
  • Numbers with an odd length: The loop condition left <= right ensures that the middle digit is not checked twice, allowing the function to handle odd-length strings correctly.
  • Non-strobogrammatic digits: If a digit is not in the dictionary or does not match its counterpart, the function returns false.