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.
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
public class Solution { public int strobogrammaticInRange(String low, String high) { int count = 0; ArrayList<String> res = new ArrayList<String>(); for (int i = low.length(); i <= high.length(); i++) { res.addAll(helper(i, i)); } for (String s : res) { if ((s.length() == low.length() && s.compareTo(low) < 0)|| (s.length() == high.length() && s.compareTo(high) > 0)) { continue; } count++; } return count; } public ArrayList<String> helper(int m, int n) { if (m == 0) { return new ArrayList(Arrays.asList("")); } else if (m == 1) { return new ArrayList(Arrays.asList("0", "1", "8")); } ArrayList<String> cur = helper(m - 2, n); ArrayList<String> tem = new ArrayList<String>(); for (String s : cur) { if (m != n) { tem.add("0" + s + "0"); } tem.add("1" + s + "1"); tem.add("8" + s + "8"); tem.add("6" + s + "9"); tem.add("9" + s + "6"); } return tem; } }
没有评论:
发表评论