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.
For example,
Given low = “50”, high = “100”, return 3. Because 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.
Solution:
1. public class Solution {
2. int count = 0;
3. String[][] pairs = {{"0", "0"}, {"1", "1"}, {"6", "9"}, {"8", "8"}, {"9", "6"}};
4. 5. public int strobogrammaticInRange(String low, String high) {
6. Map<Integer, List> map = new HashMap<Integer, List>();
7. map.put(0, new ArrayList(Arrays.asList("")));
8. map.put(1, new ArrayList(Arrays.asList("0", "1", "8")));
9. 10. for (int i = low.length(); i <= high.length(); i++)
11. helper(i, map, low, high);
12. 13. return count;
14. }
15. 16. List helper(int n, Map<Integer, List> map, String low, String high) {
17. List res = new ArrayList();
18. 19. if (map.containsKey(n)) {
20. res = map.get(n);
21. } else {
22. List list = map.containsKey(n - 2) ? map.get(n - 2) : helper(n - 2, map, low, high);
23. 24. for (int i = 0; i < list.size(); i++) {
25. String s = list.get(i);
26. 27. for (int j = 0; j < pairs.length; j++) {
28. String v = pairs[j][0] + s + pairs[j][1];
29. 30. if (v.length() == high.length() && v.compareTo(high) > 0)
31. break;
32. 33. res.add(v);
34. }
35. }
36. 37. map.put(n, res);
38. }
39. 40. if (n >= low.length()) {
41. count += res.size();
42. 43. for (String s : res) {
44. if ((s.length() > 1 && s.charAt(0) == '0') || (s.length() == low.length() && s.compareTo(low) < 0) || (s.length() == high.length() && s.compareTo(high) > 0))
45. count--;
46. }
47. }
48. 49. return res;
50. }
51. }