Strobogrammatic Number III

hard recursion backtracking strings

Problem

Count strobogrammatic numbers in the inclusive range [low, high]. low and high are given as numeric strings.

Inputlow = "50", high = "100"

Output3

69, 88, 96 fall in [50, 100].

low

high

def strobogrammatic_in_range(low, high):
    pairs = [("0","0"),("1","1"),("6","9"),("8","8"),("9","6")]
    def gen(n, top):
        if n == 0: return [""]
        if n == 1: return ["0","1","8"]
        inner = gen(n - 2, False)
        out = []
        for a, b in pairs:
            if top and a == "0": continue
            for s in inner:
                out.append(a + s + b)
        return out
    count = 0
    for n in range(len(low), len(high) + 1):
        for s in gen(n, True):
            if (len(s) == len(low) and s < low) or (len(s) == len(high) and s > high):
                continue
            count += 1
    return count

function strobogrammaticInRange(low, high) {
  const pairs = [["0","0"],["1","1"],["6","9"],["8","8"],["9","6"]];
  function gen(n, top) {
    if (n === 0) return [""];
    if (n === 1) return ["0","1","8"];
    const inner = gen(n - 2, false);
    const out = [];
    for (const [a, b] of pairs) {
      if (top && a === "0") continue;
      for (const s of inner) out.push(a + s + b);
    }
    return out;
  }
  let count = 0;
  for (let n = low.length; n <= high.length; n++) {
    for (const s of gen(n, true)) {
      if ((s.length === low.length && s < low) || (s.length === high.length && s > high)) continue;
      count++;
    }
  }
  return count;
}

class Solution {
    String[][] pairs = {{"0","0"},{"1","1"},{"6","9"},{"8","8"},{"9","6"}};
    public int strobogrammaticInRange(String low, String high) {
        int count = 0;
        for (int n = low.length(); n <= high.length(); n++) {
            for (String s : gen(n, true)) {
                if ((s.length() == low.length() && s.compareTo(low) < 0) ||
                    (s.length() == high.length() && s.compareTo(high) > 0)) continue;
                count++;
            }
        }
        return count;
    }
    List gen(int n, boolean top) {
        if (n == 0) return List.of("");
        if (n == 1) return List.of("0","1","8");
        List inner = gen(n - 2, false), out = new ArrayList<>();
        for (String[] p : pairs) {
            if (top && p[0].equals("0")) continue;
            for (String s : inner) out.add(p[0] + s + p[1]);
        }
        return out;
    }
}

class Solution {
    vector> pairs = {{"0","0"},{"1","1"},{"6","9"},{"8","8"},{"9","6"}};
    vector gen(int n, bool top) {
        if (n == 0) return {""};
        if (n == 1) return {"0","1","8"};
        auto inner = gen(n - 2, false);
        vector out;
        for (auto& [a,b] : pairs) {
            if (top && a == "0") continue;
            for (auto& s : inner) out.push_back(a + s + b);
        }
        return out;
    }
public:
    int strobogrammaticInRange(string low, string high) {
        int count = 0;
        for (int n = low.size(); n <= (int)high.size(); n++)
            for (auto& s : gen(n, true)) {
                if ((s.size() == low.size() && s < low) ||
                    (s.size() == high.size() && s > high)) continue;
                count++;
            }
        return count;
    }
};

Explanation

Here we count strobogrammatic numbers (ones that look the same flipped 180°) that fall in the range [low, high]. The plan is to generate all such numbers and tally the ones inside the range.

The helper gen(n, top) builds every strobogrammatic string of length n the same outside-in way as before: wrap a rotation pair (0-0, 1-1, 8-8, 6-9, 9-6) around a smaller valid core, skipping a leading 0 on the outermost layer.

Since any number in the range has a length between len(low) and len(high), we loop over each possible length and generate all strobogrammatic strings of that length.

For each candidate we use a string comparison to filter the edges: if its length equals low's length and it sorts below low, or equals high's length and sorts above high, we skip it. Because all strings here have the same length when compared, lexicographic order matches numeric order. Everything else increments count.

Example: low = "50", high = "100". The length-2 strobogrammatic numbers 69, 88, 96 fall inside the range, so the answer is 3.

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