Skip to content

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<pair<char, char>> 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[str], 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