My simple O(1) Java solution with explanation


  • 0

    Explanation

    The main idea is to calculate the Strobogrammatic Number amount between low and high. My optimization is to calculate the amount directly by string length with O(1) time, instead of building the combinations with O(5^(n/2)), approximate O(5^n).

    Additionally, We need to build the combinations for the specific low length and high length, this operation still needs O(5^(n/2)) time, but we spare the time for building the combinations in the range between (lowLength, hightLength).

    Thanks for viewing, any advice appreciated!

    int strobogrammaticCountByLen(int n) {
    	int count = 0;
    	if (n == 1) 
    		return 3;
    	if (n % 2 == 0) 
    		count = 4 * (int) Math.pow(5, n / 2 - 1);		//n=even
    	else 
    		count = (4 * 3) * (int) Math.pow(5, n / 2 - 1);	//n=odd
    	return count;
    }
    

    The Code

    public int strobogrammaticInRange(String low, String high) {
        	int lowLen = low.length(), highLen = high.length(), count = 0;
        	for (int i = lowLen; i <= highLen; i++) {
        		if (i == lowLen || i == highLen) {
        			for (String str : helper(i, i)) {					
        				if ((i == lowLen && str.compareTo(low) < 0) || (i == highLen && str.compareTo(high) > 0))
        					continue;
        				count++;	
        			}
        		} else {
        			count += strobogrammaticCountByLen(i);			
        		}
        	}
        	return count;
        }
        
        /* 
         * For the first pair, we have 4 candidates: 1, 8, 6, 9 (excludes 0);
         * For every pair, we have 5 candidates: 0, 1, 8, 6, 9 ; 
         * For the mid of odd length, we have 3 candidates: 0, 1, 8.
         */
        int strobogrammaticCountByLen(int n) {
        	int count = 0;
        	if (n == 1) 
        		return 3;
        	if (n % 2 == 0) 
        		count = 4 * (int) Math.pow(5, n / 2 - 1);		//n=even
        	else 
        		count = (4 * 3) * (int) Math.pow(5, n / 2 - 1);	//n=odd
        	return count;
        }
        
        public List<String> helper(int n, int len) {
        	if (n == 0) return new ArrayList<String>(Arrays.asList(""));		
        	if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        	
        	List<String> list = helper(n-2, len);
        	List<String> ret = new ArrayList<String>();
        	for (String s : list) {
        		if (n != len) ret.add("0" + s + "0");
        		ret.add("1" + s + "1");
        		ret.add("8" + s + "8");
        		ret.add("6" + s + "9");
        		ret.add("9" + s + "6");				
        	}
        	return ret;
        }

  • 0

    Technically this is still O(5^n), but faster than the un-optimized version.


Log in to reply
 

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