Clear Java AC solution using Strobogrammatic Number II method


  • 29
    C

    The basic idea is to find generate a list of strobogrammatic number with the length between the length of lower bound and the length of upper bound. Then we pass the list and ignore the numbers with the same length of lower bound or upper bound but not in the range.

    I think it is not a a very optimized method and can any one provide a better one?

    public class Solution{
    
    
    	public int strobogrammaticInRange(String low, String high){
    		int count = 0;
    		List<String> rst = new ArrayList<String>();
    		for(int n = low.length(); n <= high.length(); n++){
    			rst.addAll(helper(n, n));
    		}
    		for(String num : rst){
    		    
    			if((num.length() == low.length()&&num.compareTo(low) < 0 ) ||(num.length() == high.length() && num.compareTo(high) > 0)) continue;
    				count++;
    		}
    		return count;
    	}
    
    	private List<String> helper(int cur, int max){
    		if(cur == 0) return new ArrayList<String>(Arrays.asList(""));
    		if(cur == 1) return new ArrayList<String>(Arrays.asList("1", "8", "0"));
    
    		List<String> rst = new ArrayList<String>();
    		List<String> center = helper(cur - 2, max);
    
    		for(int i = 0; i < center.size(); i++){
    			String tmp = center.get(i);
    			if(cur != max) rst.add("0" + tmp + "0");
    			rst.add("1" + tmp + "1");
    			rst.add("6" + tmp + "9");
    			rst.add("8" + tmp + "8");
    			rst.add("9" + tmp + "6");
    		}
    		return rst;
    	}
    }

  • 7
    J

    Same Algorithm, but just use O(1) Space. :)

    public class Solution {
    public class Wrapper{
        int cnt = 0;
    }
    
    public int strobogrammaticInRange(String low, String high) {
        Wrapper w = new Wrapper();
        for(int i = low.length(); i <= high.length(); i++){
            help(w, "", i, low, high);
            help(w, "0", i, low, high);
            help(w, "1", i, low, high);
            help(w, "8", i, low, high);
        }
        return w.cnt;
    }
    
    //w:      used to record the number of valid Strobogrammatic Number
    //path:   current string
    //len:    the limit string length
    //low:    the lower bound
    //high:   the upper bound
    public void help(Wrapper w, String path, int len, String low, String high){
        if(path.length() >= len){
            //Invalid String path
            if(path.length() != len || (len != 1 && path.charAt(path.length()-1) == '0')){
                return;
            }
            //If low and high both have the same length
            else if(low.length() == high.length()){
                if(path.compareTo(low) >= 0 && path.compareTo(high) <= 0){
                    w.cnt ++;
                }
                return;
            }
           //If low and high have different lengthes
            else{
                if(len == low.length() && path.compareTo(low) >= 0){
                    w.cnt ++;
                }
                else if(len == high.length() && path.compareTo(high) <= 0){
                    w.cnt ++;
                }
                else if(len > low.length() && len < high.length()){
                    w.cnt ++;
                }
                return;
            }
        }
        
        help(w, "0"+path+"0", len, low, high);
        help(w, "1"+path+"1", len, low, high);
        help(w, "6"+path+"9", len, low, high);
        help(w, "8"+path+"8", len, low, high);
        help(w, "9"+path+"6", len, low, high);
    }
    }

  • 0
    Y

    Didn't you get memory limit exceed?..


  • 0
    C

    I didn't. Just saw this reply. ..


  • 0
    C

    But yes I am always hesitated to use string concatenation


  • 0
    Y

    Oh... I think it is not needed to generate all the strings with length > low.length() and < high.length(), that part can be done with DP. Also generating all of them is like BFS, which needs more memory than DFS.


  • 0
    C

    You are right, I'll try to think about a DP solution


  • 0
    B

    This is even faster than using the algorithm with hashmap to memorize things. Is this because every length will only be called once?


  • 2
    E

    I think you can get the length of low len1 and length of high len2. Only use strobogrammatic number 2 method to generate the strings of len1 and len2 and compare those strings with low and high. For strings between len1 and len2, you can write another recursion function that only count the number of strings rather than generating strings. It should be faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.