A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.

Example 1:
Input: “69”
Output: true

Example 2:
Input: “88”
Output: true

Example 3:
Input: “962”
Output: false

The digits of 1, 6, 9, 8, 0 when rotated 180 degrees are valid while the rest are invalid. Therefore, if we meet invalid digits, we can simply return false. Otherwise, we can construct the rotated version and then compare to the origin – a strobogrammatic number if its rotated version is the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isStrobogrammatic(string num) {
        string x = "";
        for (int i = 0; i < num.size(); ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 1: x = "1" + x; break;
                case 6: x = "9" + x; break;
                case 9: x = "6" + x; break;
                case 8: x = "8" + x; break;
                case 0: x = "0" + x; break;
            }
        }
        return x == num;
    }
};

class Solution {
public:
    bool isStrobogrammatic(string num) {
        string x = "";
        for (int i = 0; i < num.size(); ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 1: x = "1" + x; break;
                case 6: x = "9" + x; break;
                case 9: x = "6" + x; break;
                case 8: x = "8" + x; break;
                case 0: x = "0" + x; break;
            }
        }
        return x == num;
    }
};

The string concatenation may take O(N) complexity in the worst case, thus the above complexity is actually O(N^2). If we think about it, we don’t need to construct the rotated version, we just need to check if the current digit when rotated equals to another digit at the other side, thus we have the following improved version, which just runs at O(N) and O(1) space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isStrobogrammatic(string num) {
        int len = num.size();
        for (int i = 0; i < len; ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 6: if ('9' != num[len - 1 - i]) return false; break;
                case 9: if ('6' != num[len - 1 - i]) return false; break;
                case 1:
                case 8: 
                case 0: if (num[i] != num[len - 1 - i]) return false; break;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isStrobogrammatic(string num) {
        int len = num.size();
        for (int i = 0; i < len; ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 6: if ('9' != num[len - 1 - i]) return false; break;
                case 9: if ('6' != num[len - 1 - i]) return false; break;
                case 1:
                case 8: 
                case 0: if (num[i] != num[len - 1 - i]) return false; break;
            }
        }
        return true;
    }
};

To generate the Strobogrammatic numbers of Size N, we can still use the Recursive Depth First Search Algorithm: Depth First Search Algorithm to Find the Strobogrammatic Number of Given Length

–EOF (The Ultimate Computing & Technology Blog) —