Strobogrammatic Number III

This page explains Java solution to problem Strobogrammatic Number III using HashMap data structure.

Problem Statement

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low

Input: low = "50", high = "100"
Output: 3
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Solution

package com.vc.hard;

import java.util.*;

class StrobogrammaticNumberIii {
    int res = 0;
    public int strobogrammaticInRange(String low, String high) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('0', '0');
        map.put('1', '1');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');

        long lo = Long.parseLong(low);
        long hi = Long.parseLong(high);
        for(int i = low.length(); i <= high.length(); i++) {
            solve(new char[i], map, 0, i - 1, lo, hi);
        }
        return res;
    }

    private void solve(char[] number, HashMap<Character, Character> map,
                       int left, int right,
                       long lo, long hi) {
        if(left > right) {
            long numberLong = Long.parseLong(new String(number));
            if(numberLong >= lo && numberLong <= hi) res++;
        }
        else {
            for(Map.Entry<Character, Character> entry: map.entrySet()) {
                char leftValue = entry.getKey();
                char rightValue = entry.getValue();

                number[left] = leftValue;
                number[right] = rightValue;

                if(number.length != 1 && leftValue == '0' && left == 0) continue;

                if(left == right && (leftValue == '6' || leftValue == '9')) continue;

                solve(number, map, left + 1, right - 1, lo, hi);
            }
        }
    }
}

Time Complexity

O((M - N) * 5^M) Where
M is length of input string high
N is length of input string low

Space Complexity

O(M) Where
M is length of input string high