Skip to content

246. Strobogrammatic Number πŸ”’

Description

Given a string num which represents an integer, return true if num is a strobogrammatic number.

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

 

Example 1:

Input: num = "69"
Output: true

Example 2:

Input: num = "88"
Output: true

Example 3:

Input: num = "962"
Output: false

 

Constraints:

  • 1 <= num.length <= 50
  • num consists of only digits.
  • num does not contain any leading zeros except for zero itself.

Solutions

Solution 1: Two Pointers Simulation

We define an array $d$, where $d[i]$ represents the number after rotating the digit $i$ by 180Β°. If $d[i]$ is $-1$, it means that the digit $i$ cannot be rotated 180Β° to get a valid digit.

We define two pointers $i$ and $j$, pointing to the left and right ends of the string, respectively. Then we continuously move the pointers towards the center, checking whether $d[num[i]]$ and $num[j]$ are equal. If they are not equal, it means that the string is not a strobogrammatic number, and we can directly return $false$. If $i > j$, it means that we have traversed the entire string, and we return $true$.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public boolean isStrobogrammatic(String num) {
        int[] d = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        for (int i = 0, j = num.length() - 1; i <= j; ++i, --j) {
            int a = num.charAt(i) - '0', b = num.charAt(j) - '0';
            if (d[a] != b) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool isStrobogrammatic(string num) {
        vector<int> d = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        for (int i = 0, j = num.size() - 1; i <= j; ++i, --j) {
            int a = num[i] - '0', b = num[j] - '0';
            if (d[a] != b) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func isStrobogrammatic(num string) bool {
    d := []int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
    for i, j := 0, len(num)-1; i <= j; i, j = i+1, j-1 {
        a, b := int(num[i]-'0'), int(num[j]-'0')
        if d[a] != b {
            return false
        }
    }
    return true
}

Comments