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

Constraints

• 1 <= num.length <= 50

• num consists of only digits.

• num does not contain any leading zeros except for zero itself.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: num = "69"

Output: true

Example 2

Input: num = "88"

Output: true

Example 3

Input: num = "962"

Output: false

Example 4

Input: num = "1"

Output: true

Solutions

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {

    public boolean isStrobogrammatic(String num) {
        
        // Note that using a String here and appending to it would be
        // poor programming practice.
        StringBuilder rotatedStringBuilder = new StringBuilder();
        
        // Remember that we want to loop backwards through the string
        for (int i = num.length() - 1; i >= 0; i--) {
            char c = num.charAt(i);
            if (c == '0' || c == '1' || c == '8') {
                rotatedStringBuilder.append(c);
            } else if (c == '6') {
                rotatedStringBuilder.append('9');
            } else if (c == '9') {
                rotatedStringBuilder.append('6');
            } else { // This must be an invalid digit.
                return false;
            }
        }
        
        String rotatedString = rotatedStringBuilder.toString();
        return num.equals(rotatedString);
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */
 
 class Solution {
    public boolean isStrobogrammatic(String num) {
        Map<Character, Character> dict = Map.of('0', '0',
                                                '1', '1',
                                                '6', '9',
                                                '8', '8',
                                                '9', '6');
        int left = 0, right = num.length()-1;
        
        while(left <= right) {
            if(!dict.containsKey(num.charAt(left)) || 
               !dict.get(num.charAt(left)).equals(num.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

Follow up