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 (
trueorfalse) indicating ifnumis a strobogrammatic number.
Implicit Constraints:
- The length of
numis between 1 and 50. numconsists only of digits.numdoes 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
- Create a dictionary
strob_mapthat maps each strobogrammatic digit to its counterpart. - Initialize two pointers:
leftat the start of the string andrightat the end. - Iterate while
leftis less than or equal toright:- If the character at
num[left]is not instrob_map, returnfalse. - If the character at
num[right]does not match the strobogrammatic counterpart ofnum[left], returnfalse. - Move the
leftpointer one step to the right and therightpointer one step to the left.
- If the character at
- 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_mapincludes mappings for “0”, “1”, and “8”, which are strobogrammatic. - Numbers with an odd length: The loop condition
left <= rightensures 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.