# 248. Strobogrammatic Number III

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public: int strobogrammaticInRange(string low, string high) { int ans = 0; for (int n = low.length(); n <= high.length(); ++n) { string s(n, ' '); dfs(low, high, s, 0, n - 1, ans); } return ans; } private: const vector> pairs{ {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}}; void dfs(const string& low, const string& high, string& s, int l, int r, int& ans) { if (l > r) { if (s.length() == low.length() && s < low) return; if (s.length() == high.length() && s > high) return; ++ans; return; } for (const auto& [leftDigit, rightDigit] : pairs) { if (l == r && leftDigit != rightDigit) continue; s[l] = leftDigit; s[r] = rightDigit; if (s.length() > 1 && s[0] == '0') continue; dfs(low, high, s, l + 1, r - 1, ans); } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int strobogrammaticInRange(String low, String high) { for (int n = low.length(); n <= high.length(); ++n) { char[] c = new char[n]; dfs(low, high, c, 0, n - 1); } return ans; } private int ans = 0; private static final char[][] pairs = { {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}}; private void dfs(final String low, final String high, char[] c, int l, int r) { if (l > r) { final String s = new String(c); if (s.length() == low.length() && s.compareTo(low) < 0) return; if (s.length() == high.length() && s.compareTo(high) > 0) return; ++ans; return; } for (char[] pair : pairs) { if (l == r && pair[0] != pair[1]) continue; c[l] = pair[0]; c[r] = pair[1]; if (c.length > 1 && c[0] == '0') continue; dfs(low, high, c, l + 1, r - 1); } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution: def strobogrammaticInRange(self, low: str, high: str) -> int: pairs = [['0', '0'], ['1', '1'], ['6', '9'], ['8', '8'], ['9', '6']] ans = 0 def dfs(s: List[chr], l: int, r: int) -> None: nonlocal ans if l > r: if len(s) == len(low) and ''.join(s) < low: return if len(s) == len(high) and ''.join(s) > high: return ans += 1 return for leftDigit, rightDigit in pairs: if l == r and leftDigit != rightDigit: continue s[l] = leftDigit s[r] = rightDigit if len(s) > 1 and s[0] == '0': continue dfs(s, l + 1, r - 1) for n in range(len(low), len(high) + 1): dfs([' '] * n, 0, n - 1) return ans