This problem asks to determine if a given number is a strobogrammatic number, meaning it looks the same when rotated 180 degrees. The solution uses a two-pointer approach for efficiency.
Approach:
Mapping Rotations: We create a mapping (using an array d
in the code) to represent how digits transform when rotated 180 degrees. For example, 0
maps to 0
, 1
to 1
, 6
to 9
, 8
to 8
, and 9
to 6
. Digits like 2
, 3
, 4
, 5
, and 7
don't have strobogrammatic counterparts, so they're mapped to -1
.
Two-Pointer Comparison: We use two pointers, i
and j
, initially pointing to the beginning and end of the input string num
respectively. We iterate inwards, comparing the digits at i
and j
.
Validation: For each pair of digits, we check if d[num[i]]
(the rotated version of the digit at i
) is equal to num[j]
. If they are not equal, the number is not strobogrammatic, and we return false
.
Completion: If the loop completes without finding any mismatches (i.e., i
becomes greater than j
), it means all digit pairs satisfy the condition, and we return true
.
Time Complexity: O(n), where n is the length of the input string. We iterate through the string at most once.
Space Complexity: O(1). The space used by the d
array is constant, regardless of the input size.
Code Examples:
The code provided shows implementations in Python, Java, C++, and Go. All implementations follow the same algorithm:
d
array is created to map the digits.while
or for
loop iterates from both ends of the string towards the center.d[num[i]] != num[j]
checks for strobogrammatic correspondence.true
if all pairs match, false
otherwise.Example Breakdown (Python):
class Solution:
def isStrobogrammatic(self, num: str) -> bool:
d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
i, j = 0, len(num) - 1
while i <= j:
a, b = int(num[i]), int(num[j])
if d[a] != b:
return False
i, j = i + 1, j - 1
return True
Let's trace this with the input "69":
i = 0
, j = 1
a = 6
, b = 9
d[6] = 9
, which equals b
.i
increments, j
decrements; the loop condition i <= j
is no longer true, so the loop ends.True
.The other language implementations work in a very similar manner, differing only in syntax and data structure specifics.