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 and high consist of only digits.
  • low <= high
  • low and high 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
    }
    

All Problems

All Solutions