LeetCode 247: Strobogrammatic Number II Solution

Master LeetCode problem 247 (Strobogrammatic Number II), a medium 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.

247. Strobogrammatic Number II

Medium

Array String Recursion

Problem Explanation

Explanation:

To solve this problem, we can use a recursive approach to generate all strobogrammatic numbers of length n. We can start with the base cases for n = 0 and n = 1, and then recursively build strobogrammatic numbers of length n based on the numbers of length n-2.

Algorithm:

Initialize a list to store the strobogrammatic numbers of length n.
Handle the base cases for n = 0 and n = 1.
Recursively generate strobogrammatic numbers of length n-2.
For each pair of strobogrammatic numbers of length n-2, add the valid strobogrammatic numbers of length n by adding 0 and 1 to both ends of the pair.
If n is not equal to the desired length, add 8 at the center if it is not the last digit.
Return the list of strobogrammatic numbers of length n.

Time Complexity: O(5^(n/2)) where n is the length of the strobogrammatic numbers. Space Complexity: O(5^(n/2)) for storing the result.

Solution Code

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    private List<String> helper(int n, int m) {
        if (n == 0) return new ArrayList<>(Arrays.asList(""));
        if (n == 1) return new ArrayList<>(Arrays.asList("0", "1", "8"));
        
        List<String> list = helper(n - 2, m);
        List<String> res = new ArrayList<>();
        
        for (String s : list) {
            if (n != m) res.add("0" + s + "0");
            res.add("1" + s + "1");
            res.add("6" + s + "9");
            res.add("8" + s + "8");
            res.add("9" + s + "6");
        }
        
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 247 (Strobogrammatic Number II)?

This page provides optimized solutions for LeetCode problem 247 (Strobogrammatic Number II) 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 247 (Strobogrammatic Number II)?

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

Can I run code for LeetCode 247 on DevExCode?

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

Back to LeetCode Solutions