LeetCode 248: Strobogrammatic Number III Solution

Master LeetCode problem 248 (Strobogrammatic Number III), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

248. Strobogrammatic Number III

Hard

Array String Recursion

Problem Explanation

Explanation:

This problem asks us to find the number of strobogrammatic numbers in the range between a given low and high number, inclusive. A strobogrammatic number is a number that appears the same when rotated 180 degrees. For example, 69, 88, and 818 are strobogrammatic numbers.

To solve this problem, we can use a recursive approach to generate all strobogrammatic numbers within the given range and count them. We need to consider different cases for the length of the numbers and the lower and upper bounds.

Algorithm:

Initialize a list to store all strobogrammatic numbers within the range.
Create a helper function to recursively generate strobogrammatic numbers with the given length and prefix.
In the helper function, if the length is reached, check if the number is within the range. If it is, add it to the list of strobogrammatic numbers.
For each length from the lower bound to the upper bound, call the helper function to generate strobogrammatic numbers.
Handle edge cases where the lower and upper bounds have the same number of digits and check if they are strobogrammatic.

Time Complexity:

The time complexity of this algorithm is O(5^(n/2)), where n is the length of the range.

Space Complexity:

The space complexity of this algorithm is also O(5^(n/2)) due to the recursive function calls and the storage of strobogrammatic numbers. :

Solution Code

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int[] count = {0};
        for (int len = low.length(); len <= high.length(); len++) {
            generateStrobogrammatic(len, "", low, high, count);
            generateStrobogrammatic(len, "0", low, high, count);
            generateStrobogrammatic(len, "1", low, high, count);
            generateStrobogrammatic(len, "8", low, high, count);
        }
        return count[0];
    }
    
    private void generateStrobogrammatic(int len, String num, String low, String high, int[] count) {
        if (num.length() >= len) {
            if ((num.length() == low.length() && num.compareTo(low) < 0) ||
                (num.length() == high.length() && num.compareTo(high) > 0)) {
                    return;
            }
            count[0]++;
        }
        
        if (len - num.length() >= 2) {
            generateStrobogrammatic(len, "0" + num + "0", low, high, count);
            generateStrobogrammatic(len, "1" + num + "1", low, high, count);
            generateStrobogrammatic(len, "6" + num + "9", low, high, count);
            generateStrobogrammatic(len, "8" + num + "8", low, high, count);
            generateStrobogrammatic(len, "9" + num + "6", low, high, count);
        }
        
        if (len - num.length() == 1) {
            generateStrobogrammatic(len, "0" + num + "0", low, high, count);
            generateStrobogrammatic(len, "1" + num + "1", low, high, count);
            generateStrobogrammatic(len, "8" + num + "8", low, high, count);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 248 (Strobogrammatic Number III)?

This page provides optimized solutions for LeetCode problem 248 (Strobogrammatic Number III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 248 (Strobogrammatic Number III)?

The time complexity for LeetCode 248 (Strobogrammatic Number III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 248 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 248 in Java, C++, or Python.

Back to LeetCode Solutions