248.Strobogrammatic-Number-III

248. Strobogrammatic Number III

题目地址

https://leetcode.com/problems/strobogrammatic-number-iii/

题目描述

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:
Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

代码

Approach #1

class Solution {
  public int strobogrammaticInRange(String low, String high) {
    List<String> list = new ArrayList<>();
    for (int l = low.length(); l <= high.length(); l++) {
      list.addAll(findStrobogrammatic(l));
    }

    int count = 0;
    for (String s: list) {
      if ((s.length() == low.length() && s.compareTo(low) < 0)
         || (s.length() == high.length() && s.compare(high) > 0)) {
        continue;
      }
      ++count;
    }
    return count;
  }

  private List<String> findStrobogrammatic(int len) {
    List<String> list = len % 2 == 0 ? 
      Arrays.asList("") : Arrays.asList("0", "1", "8");

    for (int i = len % 2 == 0 ? 0 : 1; i < len; i += 2) {
      List<String> newList = new ArrayList<>();
      for (String s: list) {
        if (i + 2 < len) {
          newList.add("0" + s + "0");
        }

        newList.add("1" + s + "1");
        newList.add("6" + s + "9");
        newList.add("8" + s + "8");
        newList.add("9" + s + "6");
      }

      list = newList;
    }
    return list;
  }
}

Approach #2

Time: O(1) && Space: O(1)

class Solution {
  private static final char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
  public int strobogrammaticInRange(String low, String high) {
        int[] count = {0};
    for (int len = low.length(); len <= high.length(); len++) {
      char[] c = new char[len];
      dfs(low, high, c, 0, len - 1, count);
    }
    return count[0];
  }

  public void dfs(String low, String high, char[] c, int left, int right, int[] count) {
    if (left > right) {
      String s = new String(c);
      if ((s.length() == low.length() && s.compareTo(low) < 0) || (s.length() == high.length() && s.compareTo(high) > 0)) {
        return;
      }
      count[0]++;
      return;
    }

    for (char[] p: pairs) {
      c[left] = p[0];
      c[right] = p[1];
      if (c.length != 1 && c[0] == '0') {
        continue;
      }
      if (left == right && p[0] != p[1]) {
        continue;
      }
      dfs(low, high, c, left + 1, right - 1, count);
    }
  }
}