LeetCode [248] Strobogrammatic Number III

248. Strobogrammatic Number III

Hard

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.

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 { public int strobogrammaticInRange(String low, String high) { int ret = 0; for(int i = low.length(); i<=high.length(); ++i){ List<String> list = compose(i, i); for(String s : list){ if(Long.parseLong(s)>=Long.parseLong(low) && Long.parseLong(s)<=Long.parseLong(high)) ret++; } } return ret; } List<String> compose(int n, int N){ List<String> list = new ArrayList<>(); if(n==0){ list.add(""); }else if(n==1){ list.addAll(Arrays.asList("0", "1", "8")); }else{ List<String> tmp = compose(n-2, N); for(String s : tmp){ list.addAll(Arrays.asList("1"+s+"1","8"+s+"8","6"+s+"9","9"+s+"6")); if(n<N) list.add("0"+s+"0"); } } return list; } }