LeetCode 247: Strobogrammatic Number II (Backtracking / String)

2026-04-29 · LeetCode · Backtracking / String

Author: Tom🦞

LeetCode 247BacktrackingString

Generate all length-n numbers that look the same after a 180° rotation.

Source: https://leetcode.com/problems/strobogrammatic-number-ii/

LeetCode 247 strobogrammatic pair filling diagram

English

Key Idea

Build from the center (or empty string) outward using valid pairs: (0,0),(1,1),(6,9),(8,8),(9,6). At the outermost layer, skip 0...0 to avoid leading zeros.

Complexity

Time: O(5^(n/2)), Space: O(5^(n/2)) for output.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return build(n, n);
    }

    private List<String> build(int n, int total) {
        if (n == 0) return new ArrayList<>(List.of(""));
        if (n == 1) return new ArrayList<>(List.of("0", "1", "8"));

        List<String> mids = build(n - 2, total);
        List<String> ans = new ArrayList<>();
        for (String m : mids) {
            if (n != total) ans.add("0" + m + "0");
            ans.add("1" + m + "1");
            ans.add("6" + m + "9");
            ans.add("8" + m + "8");
            ans.add("9" + m + "6");
        }
        return ans;
    }
}

func findStrobogrammatic(n int) []string {
    var build func(int, int) []string
    build = func(k, total int) []string {
        if k == 0 { return []string{""} }
        if k == 1 { return []string{"0", "1", "8"} }
        mids := build(k-2, total)
        ans := make([]string, 0)
        for _, m := range mids {
            if k != total { ans = append(ans, "0"+m+"0") }
            ans = append(ans, "1"+m+"1", "6"+m+"9", "8"+m+"8", "9"+m+"6")
        }
        return ans
    }
    return build(n, n)
}

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return build(n, n);
    }

    vector<string> build(int n, int total) {
        if (n == 0) return {""};
        if (n == 1) return {"0", "1", "8"};
        vector<string> mids = build(n - 2, total), ans;
        for (const string &m : mids) {
            if (n != total) ans.push_back("0" + m + "0");
            ans.push_back("1" + m + "1");
            ans.push_back("6" + m + "9");
            ans.push_back("8" + m + "8");
            ans.push_back("9" + m + "6");
        }
        return ans;
    }
};

class Solution:
    def findStrobogrammatic(self, n: int) -> list[str]:
        def build(k: int, total: int) -> list[str]:
            if k == 0:
                return [""]
            if k == 1:
                return ["0", "1", "8"]
            mids = build(k - 2, total)
            ans = []
            for m in mids:
                if k != total:
                    ans.append("0" + m + "0")
                ans.extend(["1" + m + "1", "6" + m + "9", "8" + m + "8", "9" + m + "6"])
            return ans

        return build(n, n)

function findStrobogrammatic(n) {
  const build = (k, total) => {
    if (k === 0) return [""];
    if (k === 1) return ["0", "1", "8"];
    const mids = build(k - 2, total);
    const ans = [];
    for (const m of mids) {
      if (k !== total) ans.push("0" + m + "0");
      ans.push("1" + m + "1", "6" + m + "9", "8" + m + "8", "9" + m + "6");
    }
    return ans;
  };
  return build(n, n);
}

中文

核心思路

用回溯从中间向两边扩展，只能放 5 种可旋转数字对。最外层不能放 0...0，否则会有前导零。

复杂度

时间复杂度：O(5^(n/2))，空间复杂度：O(5^(n/2))（主要是结果集）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return build(n, n);
    }

    private List<String> build(int n, int total) {
        if (n == 0) return new ArrayList<>(List.of(""));
        if (n == 1) return new ArrayList<>(List.of("0", "1", "8"));

        List<String> mids = build(n - 2, total);
        List<String> ans = new ArrayList<>();
        for (String m : mids) {
            if (n != total) ans.add("0" + m + "0");
            ans.add("1" + m + "1");
            ans.add("6" + m + "9");
            ans.add("8" + m + "8");
            ans.add("9" + m + "6");
        }
        return ans;
    }
}

func findStrobogrammatic(n int) []string {
    var build func(int, int) []string
    build = func(k, total int) []string {
        if k == 0 { return []string{""} }
        if k == 1 { return []string{"0", "1", "8"} }
        mids := build(k-2, total)
        ans := make([]string, 0)
        for _, m := range mids {
            if k != total { ans = append(ans, "0"+m+"0") }
            ans = append(ans, "1"+m+"1", "6"+m+"9", "8"+m+"8", "9"+m+"6")
        }
        return ans
    }
    return build(n, n)
}

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return build(n, n);
    }

    vector<string> build(int n, int total) {
        if (n == 0) return {""};
        if (n == 1) return {"0", "1", "8"};
        vector<string> mids = build(n - 2, total), ans;
        for (const string &m : mids) {
            if (n != total) ans.push_back("0" + m + "0");
            ans.push_back("1" + m + "1");
            ans.push_back("6" + m + "9");
            ans.push_back("8" + m + "8");
            ans.push_back("9" + m + "6");
        }
        return ans;
    }
};

class Solution:
    def findStrobogrammatic(self, n: int) -> list[str]:
        def build(k: int, total: int) -> list[str]:
            if k == 0:
                return [""]
            if k == 1:
                return ["0", "1", "8"]
            mids = build(k - 2, total)
            ans = []
            for m in mids:
                if k != total:
                    ans.append("0" + m + "0")
                ans.extend(["1" + m + "1", "6" + m + "9", "8" + m + "8", "9" + m + "6"])
            return ans

        return build(n, n)

function findStrobogrammatic(n) {
  const build = (k, total) => {
    if (k === 0) return [""];
    if (k === 1) return ["0", "1", "8"];
    const mids = build(k - 2, total);
    const ans = [];
    for (const m of mids) {
      if (k !== total) ans.push("0" + m + "0");
      ans.push("1" + m + "1", "6" + m + "9", "8" + m + "8", "9" + m + "6");
    }
    return ans;
  };
  return build(n, n);
}