Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/248.html
Given two strings low and high that represent two integers low
and high
where low <= high
, return the number of strobogrammatic numbers in the range [low, high]
.
A strobogrammatic number is a number that looks the same when rotated 180
degrees (looked at upside down).
Example 1:
Input: low = "50", high = "100" Output: 3
Example 2:
Input: low = "0", high = "0" Output: 1
Constraints:
1 <= low.length, high.length <= 15
low
andhigh
consist of only digits.low <= high
low
andhigh
do not contain any leading zeros except for zero itself.
Algorithm
Goal is to get the number of symmetry
numbers in a given range.
Initialize the cases of n=0
and n=1
, and then recurse based on them.
The recursion length len is traversed from low to high, and then see if the current word length reaches len,
- If it is reached, first remove the multiple digits that start with 0,
- Then remove the numbers with the same length as low but less than low, and numbers with the same length as high but greater than high,
- Then the result is incremented by 1,
- Then add the five pairs of symmetric numbers to the left and right of the current word, and continue to call recursively
Code
-
public class Strobogrammatic_Number_III { public static void main(String[] args) { Strobogrammatic_Number_III out = new Strobogrammatic_Number_III(); Solution s = out.new Solution(); System.out.println(s.strobogrammaticInRange("50", "100")); } public class Solution { int res = 0; public int strobogrammaticInRange(String low, String high) { if (low == null || high == null) { return res; } for (int i = low.length(); i <= high.length(); ++i) { dfs(low, high, "", i); dfs(low, high, "0", i); dfs(low, high, "1", i); dfs(low, high, "8", i); } return res; } void dfs(String low, String high, String path, int len) { if (path.length() >= len) { if (path.length() != len || (len != 1 && path.charAt(0) == '0')) { return; } if ((len == low.length() && path.compareTo(low) < 0) || (len == high.length() && path.compareTo(high) > 0)) { return; } ++res; } dfs(low, high, "0" + path + "0", len); dfs(low, high, "1" + path + "1", len); dfs(low, high, "6" + path + "9", len); dfs(low, high, "8" + path + "8", len); dfs(low, high, "9" + path + "6", len); } } } ############ class Solution { private static final int[][] PAIRS = { {1, 1}, {8, 8}, {6, 9}, {9, 6}}; private int n; public int strobogrammaticInRange(String low, String high) { int a = low.length(), b = high.length(); long l = Long.parseLong(low), r = Long.parseLong(high); int ans = 0; for (n = a; n <= b; ++n) { for (String s : dfs(n)) { long v = Long.parseLong(s); if (l <= v && v <= r) { ++ans; } } } return ans; } 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; } }
-
using ll = long long; class Solution { public: const vector<pair<char, char>> pairs = { {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'} }; int strobogrammaticInRange(string low, string high) { 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; }; int a = low.size(), b = high.size(); int ans = 0; ll l = stoll(low), r = stoll(high); for (n = a; n <= b; ++n) { for (auto& s : dfs(n)) { ll v = stoll(s); if (l <= v && v <= r) { ++ans; } } } return ans; } };
-
''' >>> 'abc' < 'def' True >>> 'abc' < 'aef' True >>> 'abc' < 'aaf' False ''' class Solution: def strobogrammaticInRange(self, low: str, high: str) -> int: self.count = 0 self.low, self.high = low, high self.dfs('') self.dfs('0') self.dfs('1') self.dfs('8') return self.count def dfs(self, s): if len(s) >= len(self.low) and len(s) <= len(self.high): if (len(s) == len(self.low) and s < self.low) or (len(s) == len(self.high) and s > self.high): return if not (len(s) > 1 and s[0] == '0'): self.count += 1 if len(s) + 2 > len(self.high): # because next step is append 2 chars at beginning and end return self.dfs('0' + s + '0') self.dfs('1' + s + '1') self.dfs('6' + s + '9') self.dfs('8' + s + '8') self.dfs('9' + s + '6') class Solution: # no trim, just check if low <= int(s) <= high def strobogrammaticInRange(self, low: str, high: str) -> int: 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 a, b = len(low), len(high) low, high = int(low), int(high) ans = 0 for n in range(a, b + 1): for s in dfs(n): # so basically no trimming applied in dfs(), just get all if low <= int(s) <= high: ans += 1 return ans ############ class Solution(object): def findStrobogrammatic(self, n): """ :type n: int :rtype: List[str] """ self.d = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"} def dfs(half, path, n): if len(path) == half: pathStr = "".join(path) if half * 2 == n: toAppend = pathStr + "".join([self.d[x] for x in pathStr[::-1]]) toAppendInt = int(toAppend) if self.low <= toAppendInt <= self.high: self.count += 1 else: for c in "018": toAppend = pathStr + c + "".join([self.d[x] for x in pathStr[::-1]]) toAppendInt = int(toAppend) if self.low <= toAppendInt <= self.high: self.count += 1 return for c in "01689": if c == "0" and len(path) == 0: continue path.append(c) dfs(half, path, n) path.pop() res = [] dfs(n / 2, [], n) return res def strobogrammaticInRange(self, low, high): """ :type low: str :type high: str :rtype: int """ if int(low) > int(high): return 0 self.count = 0 self.low = int(low) self.high = int(high) for length in range(len(low), len(high) + 1): self.findStrobogrammatic(length) return self.count
-
func strobogrammaticInRange(low string, high string) int { n := 0 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 } a, b := len(low), len(high) l, _ := strconv.Atoi(low) r, _ := strconv.Atoi(high) ans := 0 for n = a; n <= b; n++ { for _, s := range dfs(n) { v, _ := strconv.Atoi(s) if l <= v && v <= r { ans++ } } } return ans }