Java 1ms solution with inline explanation beat 96%


  • 0

    The basic idea is to generate those with length = low.length() and length = high.length() using DFS with early stopping. Stop early reduce the time from 25ms to 1ms. We add character pairs from outside toward inside. When generate those with length = low.length() if we found the prefix is less than the corresponding part in low we don't need go any further. When generate those with length = high.length() if we found the prefix is larger than the corresponding part in high we completely abort. For those with length between low.length() and high.length() we can directly get the count using dp. The basic idea is if we allow 0 to be at the beginning the count(len) = 5count(len-2), to exclude those start with 0, ans(len) = 4count(len-2)

    private int count, ans;
        private final char[] pairs = {'0', '0', '1', '1', '6', '9', '8', '8', '9', '6'};
        private int compare(String s1, String s2) {
            if (s1.length() < s2.length()) return -1;
            else if(s1.length() > s2.length()) return 1;
            for (int i = 0; i < s1.length(); i++) {
                char ch1 = s1.charAt(i), ch2 = s2.charAt(i);
                if (ch1 > ch2) return 1;
                else if (ch1 < ch2) return -1;
            }
            return 0;
        }
        private void helper(char[] chs, int start, String low, String high, boolean lo, boolean hi) {   //generate and count those with len == chs.length
            int left = start, right = chs.length - 1 - left;
            if (left > right) {
                String s = new String(chs);
                if ((s.equals("0") || s.charAt(0) != '0') && (!lo || compare(s, low) >= 0) && (!hi || compare(s, high) <= 0)) count++;
            } else {
                for (int i = 0; i < 10; i += 2) {
                    if (left == right && pairs[i] != pairs[i+1]) continue;
                    if (left == 0 && chs.length > 1 && i == 0) continue;
                    chs[left] = pairs[i];
                    chs[right] = pairs[i+1];
                    if (hi && compare(new String(chs, 0, left+1), high.substring(0, left+1)) > 0) break;    //these two lines are crucial for early stopping
                    if (lo && compare(new String(chs, 0, left+1), low.substring(0, left+1)) < 0) continue;
                    helper(chs, start+1, low, high, lo, hi);
                }
            }
        }
        public int strobogrammaticInRange(String low, String high) {
            if (compare(low, high) == 1) return 0;
            count = 0;
            ans = 0;
            int m = low.length(), n = high.length();
            if (m == n) {
                helper(new char[m], 0, low, high, true, true);
                return count;
            }
            helper(new char[m], 0, low, high, true, false);
            ans += count;
            count = 0;
            helper(new char[n], 0, low, high, false, true);
            ans += count;
            int len0 = 1, len1 = 3; //count of len = 0 is 1 {""}, count of len = 1 is 3 {"0", "1", "8"}
            for (int i = 2; i < n; i++) {
                if (i > m && i < n) ans += 4 * len0;    //count those with m < len < n using dp, cannot begin with 0 so x4 not x5
                int tmp = len0 * 5; //if we allow start with 0 count of len is count of len-2 * 5
                len0 = len1;
                len1 = tmp;
            }
            return ans;
        }
    

Log in to reply
 

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