StroboGrammatic Number

101.Strobogrammatic Number

String

Hash Table

Problem Statement:

A number is called strobogrammatic if it looks the same when rotated 180 degrees (i.e., the digit "6" becomes "9," and vice versa, while "8," "1," and "0" remain unchanged). Given a string num, determine if it is strobogrammatic.

Algorithm:

1. Create a map of valid digit pairs that are strobogrammatic (e.g., '6' ↔ '9').
2. Iterate over the first half of the string, comparing each character with its corresponding character from the other end:
   • If the character is not in the map or its mapped value does not match the corresponding character, return false.
3. For odd-length strings, check the middle character separately to ensure it is strobogrammatic ('0', '1', or '8').
4. If all checks pass, return true.

Complexity:

Time: O(n), where n is the length of the string | Space: O(1).

Java Implementation:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isStrobogrammatic(String num) {
        int n = num.length();
        Map map = new HashMap<>();
        map.put('6', '9');
        map.put('9', '6');
        map.put('8', '8');
        map.put('1', '1');
        map.put('0', '0');

        // Check pairs of digits
        for (int i = 0; i < n / 2; i++) {
            char c1 = num.charAt(i);
            char c2 = num.charAt(n - i - 1);
            if (!map.containsKey(c1) || map.get(c1) != c2)
                return false;
        }

        // Check middle digit for odd-length numbers
        if (n % 2 != 0) {
            char mid = num.charAt(n / 2);
            if (mid == '6' || mid == '9' || !map.containsKey(mid))
                return false;
        }

        return true;
    }
}
                

Python Implementation:

def isStrobogrammatic(num):
    # Define the strobogrammatic pairs
    map = {'6': '9', '9': '6', '8': '8', '1': '1', '0': '0'}
    n = len(num)

    # Check pairs of digits
    for i in range(n // 2):
        c1, c2 = num[i], num[n - i - 1]
        if c1 not in map or map[c1] != c2:
            return False

    # Check middle digit for odd-length numbers
    if n % 2 != 0:
        mid = num[n // 2]
        if mid not in {'0', '1', '8'}:
            return False

    return True
                

C++ Implementation:

#include 
#include 
using namespace std;

bool isStrobogrammatic(string num) {
    unordered_map map = {
        {'6', '9'}, {'9', '6'}, {'8', '8'}, {'1', '1'}, {'0', '0'}
    };
    int n = num.size();

    // Check pairs of digits
    for (int i = 0; i < n / 2; i++) {
        char c1 = num[i];
        char c2 = num[n - i - 1];
        if (!map.count(c1) || map[c1] != c2)
            return false;
    }

    // Check middle digit for odd-length numbers
    if (n % 2 != 0) {
        char mid = num[n / 2];
        if (mid != '0' && mid != '1' && mid != '8')
            return false;
    }

    return true;
}