Question

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

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)

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;
  }
}

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);
  }
};

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)
}