package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/numbers-with-same-consecutive-differences/
 */
public class Problem967 {
    public int[] numsSameConsecDiff(int N, int K) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i <= 9; i++) {
            List<String> newList = new ArrayList<>();
            List<String> list = numsSameConsecDiff(N - 1, K, i);
            if (list.isEmpty()) {
                String s = "" + i;
                if (s.length() == N) {
                    newList.add(s);
                }
            } else {
                for (String s : list) {
                    String s1 = i + s;
                    if (s1.length() == N) {
                        newList.add(s1);
                    }
                }
            }
            set.addAll(newList.stream()
                .filter(e -> e.length() == 1 || (e.length() > 1 && !e.startsWith("0")))
                .map(Integer::valueOf).collect(Collectors.toList()));
        }
        int[] answer = new int[set.size()];
        int i = 0;
        for (int s : set) {
            answer[i++] = s;
        }
        Arrays.sort(answer);
        return answer;
    }

    private static List<String> numsSameConsecDiff(int n, int k, int i) {
        if (n == 0) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();
        if (i + k <= 9) {
            List<String> l = numsSameConsecDiff(n - 1, k, i + k);
            if (l.isEmpty()) {
                list.add("" + (i + k));
            } else {
                for (String s : l) {
                    list.add((i + k) + s);
                }
            }
        }
        if (i - k >= 0) {
            List<String> l = numsSameConsecDiff(n - 1, k, i - k);
            if (l.isEmpty()) {
                list.add("" + (i - k));
            } else {
                for (String s : l) {
                    list.add((i - k) + s);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Problem967 prob = new Problem967();
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(3, 7))); // [181,292,707,818,929]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(2, 1))); // [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(3, 3))); // [141,147,252,258,303,363,369,414,474,525,585,630,636,696,741,747,852,858,963,969]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(9, 9))); // [909090909]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(9, 1))); // [909090909]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(1, 0))); // [0,1,2,3,4,5,6,7,8,9]
        System.out.println(Arrays.toString(prob.numsSameConsecDiff(1, 6))); // [0,1,2,3,4,5,6,7,8,9]
    }
}

@@ -44,33 +44,8 @@
 st;%0A
-import java.util.Arrays;%0A
 impo
@@ -114,44 +114,8 @@
 Set;
-%0Aimport java.util.stream.Collectors;
 %0A%0A/*
@@ -314,24 +314,77 @@
 ashSet%3C%3E();%0A
+        List%3CString%3E%5B%5D%5B%5D memo = new List%5BN + 1%5D%5B10%5D;%0A
         for 
@@ -526,16 +526,22 @@
  1, K, i
+, memo
 );%0A     
@@ -952,35 +952,34 @@
     
-set.addAll(newList.stream()
+for (String s : newList) %7B
 %0A   
@@ -995,22 +995,13 @@
     
-.filter(e -%3E e
+if (s
 .len
@@ -1015,17 +1015,17 @@
 = 1 %7C%7C (
-e
+s
 .length(
@@ -1034,17 +1034,17 @@
 %3E 1 && !
-e
+s
 .startsW
@@ -1053,17 +1053,20 @@
 h(%220%22)))
-%0A
+ %7B%0A 
         
@@ -1077,20 +1077,26 @@
     
-.map
+   set.add
 (Integer
 ::va
@@ -1095,49 +1095,53 @@
 eger
-::
+.
 valueOf
-).collect(Collectors.toList()));
+(s));%0A                %7D%0A            %7D
 %0A   
@@ -1281,37 +1281,8 @@
   %7D%0A
-        Arrays.sort(answer);%0A
     
@@ -1377,16 +1377,39 @@
 k, int i
+, List%3CString%3E%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -1466,32 +1466,107 @@
 %3C%3E();%0A        %7D%0A
+        if (memo%5Bn%5D%5Bi%5D != null) %7B%0A            return memo%5Bn%5D%5Bi%5D;%0A        %7D%0A
         List%3CStr
@@ -1685,16 +1685,22 @@
 k, i + k
+, memo
 );%0A     
@@ -1997,16 +1997,22 @@
 k, i - k
+, memo
 );%0A     
@@ -2232,894 +2232,47 @@
     
-return list;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem967 prob = new Problem967();%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(3, 7))); // %5B181,292,707,818,929%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(2, 1))); // %5B10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(3, 3))); // %5B141,147,252,258,303,363,369,414,474,525,585,630,636,696,741,747,852,858,963,969%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(9, 9))); // %5B909090909%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(9, 1))); // %5B909090909%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(1, 0))); // %5B0,1,2,3,4,5,6,7,8,9%5D%0A        System.out.println(Arrays.toString(prob.numsSameConsecDiff(1, 6))); // %5B0,1,2,3,4,5,6,7,8,9%5D
+memo%5Bn%5D%5Bi%5D = list;%0A        return list;
 %0A   

Solve problem 967