Java Solution Using DP and Strobogrammatic Number II


  • 1
    R

    Number of Strobogrammatic numbers follows:

    f(2*n) = f(2*n-1) + f(2*n-2)*2;
    f(2*n+1) = f(2*n) * 3;
    n = 1,2,3...   |   f(0) = 1, f(1) = 2;
    

    f(1) is a special case because of 0;


    public int strobogrammaticInRange(String low, String high) {
    	int h = high.length(), l = low.length();
    	if (l > h || h == l && low.compareTo(high) > 0)
    		return 0;
    	int[] dp = new int[h + 1];
    	dp[0] = 1; dp[1] = 2;
    	for (int i = 2; i <= h; i++) {
    		dp[i] = i % 2 == 0 ? dp[i - 1] + 2 * dp[i - 2] : dp[i - 1] * 3;
    	}
    	dp[1] = 3;
    	long count = findStrobogrammatic(l).stream().filter(j -> j.compareTo(low) >= 0)
    			            .count() - 
                     findStrobogrammatic(h).stream().filter(j -> j.compareTo(high) > 0)
                            .count();
    	for (int i = l + 1; i <= h; i++) {
    		count += dp[i];
    	}
    	return (int) count;
    }
    
    public List<String> findStrobogrammatic(int n) {
        List<String> ret = new ArrayList<>();
        helper(ret, new char[n], 0, n-1);
        return ret;
    }
    
    private final char[] ipick = {'0', '1', '8', '6', '9'};
    private final char[] jpick = {'0', '1', '8', '9', '6'};
    private void helper(List<String> ret, char[] tmp, int i, int j) {
        if (i > j) {
            ret.add(new String(tmp)); return;
        } 
        if (i == j){
            for (int k = 0; k < 3; k++) {
                tmp[i] = ipick[k];
                helper(ret, tmp, i+1, j-1);
            }
        } else {
            for (int k = i == 0 ? 1 : 0; k < 5; k++) {
                tmp[i] = ipick[k];
                tmp[j] = jpick[k];
                helper(ret, tmp, i+1, j-1);
            }
        }
    }

  • 0
    H

    I tested your solution. I did't find DP solution make any improvement in execution time, and it is even slower!


  • 0
    R

    Well, it's depend on the test cases. Also, I just simply use java stream which may slower than normal way by iterate the list.
    The code above costs 110ms in the Leetcode OJ. I just test the normal method to iterate the list and the result became 25ms.


  • 0
    J

    This part is slow - as we only need count, not the really string.
    long count = findStrobogrammatic(l).stream().filter(j -> j.compareTo(low) >= 0)
    .count() -
    findStrobogrammatic(h).stream().filter(j -> j.compareTo(high) > 0)
    .count();

    -find same ideas code here: https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code


Log in to reply
 

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