2015年9月10日星期四

Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
For example,
Given n = 2, return ["11","69","88","96"].

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
   
    private List<String> helper(int n, int m) {
        String single[] = {"0", "1", "8"};
        String pair[] = {"69", "96", "00", "11", "88"};
        if (n == 0) {
            return new ArrayList<String>(Arrays.asList(""));
        } else if (n == 1) {
            return new ArrayList<String>(Arrays.asList(single));
        } else {
            List<String> last = helper(n - 2, m);
            List<String> res = new ArrayList<String>();
            for (String s : last) {
                for (String p : pair) {
                    if (n == m && p.charAt(0) == '0') continue;
                    res.add(p.charAt(0) + s + p.charAt(1));
                }
            }
            return res;
        }
    }
}

没有评论:

发表评论