LIKE CODING: Recursion

Wednesday, August 5, 2015

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.

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

Tuesday, August 4, 2015

LeetCode [247] Strobogrammatic Number II

247. Strobogrammatic Number II

Medium

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.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    List<String> helper(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 = helper(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;
    }
}