Comment on page

248.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++) {
}
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) {
}
}
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);
}
}
}