248. Strobogrammatic Number III

21.52 %
class Solution {
    public int strobogrammaticInRange(String low, String high) {
        // 1 1
        // 6 9
        // 8 8
        // 9 6
        // 0 0
        int start = low.length(), end = high.length();
        List<String> rawResult = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            rawResult.addAll(helper(i));
            List<String> curr = helper(i);
        }
        int count = 0;
        for (String str : rawResult) {
            if ((str.length() > 1 && str.charAt(0) == '0')
               || (str.length() == low.length() && str.compareTo(low) < 0)
               || (str.length() == high.length() && str.compareTo(high) > 0)) continue;
            count++;
        }
        return count;
    }
   
    private List<String> helper(int len) {
        if (len == 0) return Arrays.asList(new String[]{""});
        if (len == 1) return Arrays.asList(new String[]{"0", "1", "8"});
       
        List<String> result = new ArrayList<>();
        List<String> center = helper(len - 2);
        for (String cen : center) {
            result.add("1" + cen + "1");
            result.add("6" + cen + "9");
            result.add("8" + cen + "8");
            result.add("9" + cen + "6");
            result.add("0" + cen + "0");
        }
        return result;
    }
}