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