leetcode/solution/0200-0299/0247.Strobogrammatic Number II

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/0200-0299/0247.Strobogrammatic%20Number%20II/README_EN.md	Recursion Array String

247. Strobogrammatic Number II 🔒

中文文档

Description

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

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

 

Example 1:

Input: n = 2
Output: ["11","69","88","96"]

Example 2:

Input: n = 1
Output: ["0","1","8"]

 

Constraints:

• 1 <= n <= 14

Solutions

Solution 1: Recursion

If the length is 1, then the strobogrammatic numbers are only 0, 1, 8; if the length is 2, then the strobogrammatic numbers are only 11, 69, 88, 96.

We design a recursive function dfs(u), which returns the strobogrammatic numbers of length u. The answer is dfs(n).

If u is 0, return a list containing an empty string, i.e., [""]; if u is 1, return the list ["0", "1", "8"].

If u is greater than 1, we traverse all the strobogrammatic numbers of length u - 2. For each strobogrammatic number v, we add 1, 8, 6, 9 to both sides of it, and we can get the strobogrammatic numbers of length u.

Note that if u \neq n, we can also add 0 to both sides of the strobogrammatic number.

Finally, we return all the strobogrammatic numbers of length n.

The time complexity is O(2^{n+2}).

Similar problems:

• 248. Strobogrammatic Number III 🔒

Python3

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        def dfs(u):
            if u == 0:
                return ['']
            if u == 1:
                return ['0', '1', '8']
            ans = []
            for v in dfs(u - 2):
                for l, r in ('11', '88', '69', '96'):
                    ans.append(l + v + r)
                if u != n:
                    ans.append('0' + v + '0')
            return ans

        return dfs(n)

Java

class Solution {
    private static final int[][] PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
    private int n;

    public List<String> findStrobogrammatic(int n) {
        this.n = n;
        return dfs(n);
    }

    private List<String> dfs(int u) {
        if (u == 0) {
            return Collections.singletonList("");
        }
        if (u == 1) {
            return Arrays.asList("0", "1", "8");
        }
        List<String> ans = new ArrayList<>();
        for (String v : dfs(u - 2)) {
            for (var p : PAIRS) {
                ans.add(p[0] + v + p[1]);
            }
            if (u != n) {
                ans.add(0 + v + 0);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    const vector<pair<char, char>> pairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};

    vector<string> findStrobogrammatic(int n) {
        function<vector<string>(int)> dfs = [&](int u) {
            if (u == 0) return vector<string>{""};
            if (u == 1) return vector<string>{"0", "1", "8"};
            vector<string> ans;
            for (auto& v : dfs(u - 2)) {
                for (auto& [l, r] : pairs) ans.push_back(l + v + r);
                if (u != n) ans.push_back('0' + v + '0');
            }
            return ans;
        };
        return dfs(n);
    }
};

Go

func findStrobogrammatic(n int) []string {
	var dfs func(int) []string
	dfs = func(u int) []string {
		if u == 0 {
			return []string{""}
		}
		if u == 1 {
			return []string{"0", "1", "8"}
		}
		var ans []string
		pairs := [][]string{{"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"}}
		for _, v := range dfs(u - 2) {
			for _, p := range pairs {
				ans = append(ans, p[0]+v+p[1])
			}
			if u != n {
				ans = append(ans, "0"+v+"0")
			}
		}
		return ans
	}
	return dfs(n)
}