Leetcode 247. Strobogrammatic Number II

Problem Explanation

A strobogrammatic number is a number that appears the same when flipped vertically (rotated 180 degrees). The digits 0, 1, 8 remain the same when flipped vertically, while the digits 6 and 9 become each other when flipped. We are required to find all strobogrammatic numbers of a given length n.

Let's consider an example with n =2. All possible strobogrammatic numbers will be ["11", "69", "88", "96"].

Approach

The approach is as follows:

• Call a helper function with initial parameters as n and n (let's say n and k). This function will return a list of all strobogrammatic numbers of length n. k will be used to avoid adding leading zeros.
• In the helper function, if n is 0, return an empty string. If n is 1, return all numbers that are same when upside down ["0", "1", "8"].
• For n > 1, recur for (n-2) to obtain all strobogrammatic numbers of length (n-2), then add 11, 69, 88, 96 and 00 on the two sides of the obtained numbers.
  • "0" added on both sides should be avoided for the outermost recursion to prevent leading zeroes, hence check if n is less than k before adding "0" on the two sides.
• Return the final list.

This approach uses the recursive method to solve the problem.

Python Solution

1
2python
3class Solution:
4    def findStrobogrammatic(self, n: int) -> List[str]:
5        
6        def helper(n, k):
7            if n == 0:
8                return [""]
9            if n == 1:
10                return ['0', '1', '8']
11            rec_res = helper(n - 2, k)
12            res = []
13            for s in rec_res:
14                if n != k:
15                    res.append('0' + s + '0')
16                res.append('1' + s + '1')
17                res.append('6' + s + '9')
18                res.append('8' + s + '8')
19                res.append('9' + s + '6')
20            return res
21        
22        return helper(n, n)

Java Solution

1
2java
3class Solution {
4    public List<String> findStrobogrammatic(int n) {
5        return helper(n, n);
6    }
7    
8    public ArrayList<String> helper(int n, int k) {
9        
10        if(n == 0)
11            return new ArrayList<>(Arrays.asList(""));
12        if(n == 1)
13            return new ArrayList<>(Arrays.asList("0","1", "8"));
14        
15        List<String> res = helper(n-2, k);
16        ArrayList<String> result = new ArrayList<>();
17        
18        for(String num: res) {
19            if(n != k)
20                result.add("0" + num + "0");
21            result.add("1" + num + "1");
22            result.add("6" + num + "9");
23            result.add("8" + num + "8");
24            result.add("9" + num + "6");
25        }
26        return result;
27    }
28}

JavaScript Solution

1
2javascript
3var findStrobogrammatic = function(n) {
4    return helper(n, n);
5};
6
7function helper(n, k) {
8    if(n == 0) {
9        return [''];
10    } else if(n == 1) {
11        return ['0', '1', '8'];
12    }
13    let mid = helper(n-2, k);
14    let result = [];
15    for(let i = 0; i < mid.length; i++) {
16        if(n != k) result.push('0' + mid[i] + '0');
17        result.push('1' + mid[i] + '1');
18        result.push('6' + mid[i] + '9');
19        result.push('8' + mid[i] + '8');
20        result.push('9' + mid[i] + '6');
21    }
22    return result;
23};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> findStrobogrammatic(int n) {
6        return helper(n, n);
7    }
8    
9    vector<string> helper(int n, int k) {
10        if(n == 0)
11            return {""};
12        if(n == 1)
13            return {"0", "1", "8"};
14        
15        vector<string> result;
16        
17        for(auto s: helper(n-2, k)) {
18            if(n != k)
19                result.push_back("0" + s + "0");
20            result.push_back("1" + s + "1");
21            result.push_back("6" + s + "9");
22            result.push_back("8" + s + "8");
23            result.push_back("9" + s + "6");
24        }
25        return result;
26    }
27};

C# Solution

1
2csharp
3public class Solution {
4   public IList<string> FindStrobogrammatic(int n) {
5       return Helper(n, n);
6   }
7
8   private IList<string> Helper(int n, int k) {
9       if(n == 0)
10           return new List<string>{""};
11       if(n == 1)
12           return new List<string>{"0", "1", "8"};
13       
14       var result = new List<string>();
15
16       foreach (var num in Helper(n - 2, k))
17       {
18           if (n != k)
19               result.Add("0" + num + "0");
20
21           result.Add("1" + num + "1");
22           result.Add("6" + num + "9");
23           result.Add("8" + num + "8");
24           result.Add("9" + num + "6");
25       }
26       return result;
27   }
28};

All solutions are implemented with recursive function calls to get all the strobogrammatic numbers and all these solutions have a time complexity of O(5^(n/2)) as every number is composed of one among the 5 possible numbers (0,1,6,8,9) each time and the number of digits are at max n/2. The use cases to keep track of the respective solutions have been mentioned through comments in the codes.In conclusion, the problem of finding all strobogrammatic numbers of length n is a common task that can be solved by using recursion and a helper function. The main idea is to check if the number of digits n is zero or one, then we return the base cases, else we make a recursive call that decrements n by 2 units. We use a loop to append the possible strobogrammatic units ("0", "1", "6", "8", "9") to both ends of the results of the recursive call. Leading zeros are avoided by checking if the current updated number of digits n equals to the original number of digits k.

The solutions provided can be implemented in multiple programming languages including Python, Java, JavaScript, C++, and C#, and they all follow fundamentally the same approach. Understanding and implementing this solution require strong basics in recursion and string manipulation which are vital concepts in many programming languages.

Though the time complexity is exponential due to the recursive nature of the problem, with careful implementation and understanding, such problems provide substantive potential for understanding key programming concepts. This problem is particularly useful as it touches on the substitution of digits and can be used to create similar exercises that require checking for digit substitution and validates a strong understanding of recursion through a real-life example.