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

The objective is to determine the count of symmetric numbers within a specified range.

Begin by establishing base cases for n=0 and n=1, and proceed with recursive calls based on these cases.

During the recursion, iterate from the lower to the upper limit of the range, examining if the current word length matches the target length, len:

Upon reaching the target length, initially eliminate numbers that begin with multiple zeros.
Next, exclude numbers that are of the same length as the lower limit but smaller, and numbers of the same length as the upper limit but larger.
Subsequently, increment the result count by 1.
Finally, append the five pairs of symmetric digits to both ends of the current word and continue with the recursive process.

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