0246.md

246. Strobogrammatic Number

Level:

Topic:

Question

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).\

Input: num = "69"
Output: true

Intuition

• Only 0,1,8 are the same upside down
• 6, 9 is a pair of special case where they must be in pair

Strobogrammatic is similar to palindrome but it constricts to only 4 pairs to validate.

• use two pointers, one starts from the left end and the other starts from the right end
• if string can be odd, so the while loop should be i <= j
• then compare the two pointer characters to see if they're in one of the valid pairs

Code

Time: O(n)
Space: O(1)

public boolean isStrobogrammatic(String num) {
    // 0,8,1 is identical
    // 6 and 9 are reversed

    // like palindrome but with 6 and 9 are special case

    int i = 0, j = num.length()-1;

    // store every combination of strobogrammatic number
    Map<Character, Character> map = new HashMap<>();
    map.put('0', '0');
    map.put('1', '1');
    map.put('8', '8');
    map.put('6', '9');
    map.put('9', '6');


    while (i <= j) {
        char c1 = num.charAt(i);
        char c2 = num.charAt(j);
        if (!map.containsKey(c1) || map.get(c1) != c2)
            return false;
        i++;
        j--;
    }

    return true;
}