{x}
blog image

Strobogrammatic Number

Solution Explanation: Strobogrammatic Number

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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:

  • Initialization: The d array is created to map the digits.
  • Iteration: The while or for loop iterates from both ends of the string towards the center.
  • Comparison: The comparison d[num[i]] != num[j] checks for strobogrammatic correspondence.
  • Return Value: 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":

  1. i = 0, j = 1
  2. a = 6, b = 9
  3. d[6] = 9, which equals b.
  4. i increments, j decrements; the loop condition i <= j is no longer true, so the loop ends.
  5. The function returns True.

The other language implementations work in a very similar manner, differing only in syntax and data structure specifics.