2015年10月29日星期四

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.

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;
    }
}

没有评论:

发表评论