Strobogrammatic Number II

medium recursion backtracking strings

Problem

Find all strobogrammatic numbers that are of length n. A strobogrammatic number looks the same when rotated 180°.

Inputn = 2

Output["11","69","88","96"]

Length-2 wraps a pair around the empty core; "00" is dropped (leading zero).

def find_strobogrammatic(n):
    pairs = [("0","0"),("1","1"),("6","9"),("8","8"),("9","6")]
    def build(k):
        if k == 0: return [""]
        if k == 1: return ["0","1","8"]
        inner = build(k - 2)
        out = []
        for a, b in pairs:
            if k == n and a == "0": continue
            for s in inner:
                out.append(a + s + b)
        return out
    return build(n)

function findStrobogrammatic(n) {
  const pairs = [["0","0"],["1","1"],["6","9"],["8","8"],["9","6"]];
  function build(k) {
    if (k === 0) return [""];
    if (k === 1) return ["0","1","8"];
    const inner = build(k - 2);
    const out = [];
    for (const [a, b] of pairs) {
      if (k === n && a === "0") continue;
      for (const s of inner) out.push(a + s + b);
    }
    return out;
  }
  return build(n);
}

class Solution {
    int target;
    public List findStrobogrammatic(int n) {
        target = n; return build(n);
    }
    List build(int k) {
        if (k == 0) return List.of("");
        if (k == 1) return List.of("0","1","8");
        List inner = build(k - 2);
        String[][] pairs = {{"0","0"},{"1","1"},{"6","9"},{"8","8"},{"9","6"}};
        List out = new ArrayList<>();
        for (String[] p : pairs) {
            if (k == target && p[0].equals("0")) continue;
            for (String s : inner) out.add(p[0] + s + p[1]);
        }
        return out;
    }
}

class Solution {
    int target;
    vector build(int k) {
        if (k == 0) return {""};
        if (k == 1) return {"0","1","8"};
        auto inner = build(k - 2);
        vector> pairs = {{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
        vector out;
        for (auto [a,b] : pairs) {
            if (k == target && a == '0') continue;
            for (auto& s : inner) out.push_back(string(1,a) + s + string(1,b));
        }
        return out;
    }
public:
    vector findStrobogrammatic(int n) { target = n; return build(n); }
};

Explanation

A strobogrammatic number reads the same after a 180° rotation. Only a few digit pairs survive a flip: 0-0, 1-1, 8-8, and the swapped pair 6-9 / 9-6. We build these numbers from the outside in.

The recursive build(k) makes all valid strings of length k. The base cases anchor the recursion: length 0 gives one empty core [""], and length 1 gives the digits that flip to themselves, ["0","1","8"].

For larger k, we first build every valid inner core of length k - 2, then wrap a rotation pair around it: for each pair (a, b) we form a + s + b. This guarantees the outer two characters are a valid flip of each other.

One special rule: when k == n (the outermost layer of the final answer) we skip pairs starting with 0, because a real number cannot have a leading zero.

Example: n = 2. The empty core "" gets wrapped by each pair, producing "11", "69", "88", "96" — and "00" is dropped for its leading zero.

Time: O(5^(n/2)) Space: O(5^(n/2))