LeetCode - Strobogrammatic Number III
Problem description
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:
1
2
3
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.
Analysis
Note that the ways to compose a strobogrammatic number is limited. So that we can use backtrack to do this and check if it’s in that range.
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
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);
}
}
}
What to improve
- analysis the complexity and then find the solution.