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
}

248 - Strobogrammatic Number III

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions