Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.
Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.
You may return the answer in any order.
 
Example 1:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 3:
Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]

Example 4:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 5:
Input: n = 2, k = 2
Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

 
Constraints:

2 <= n <= 9
0 <= k <= 9

Difficulty: interview

Starter code:

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        

Solutions:
class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        # DFS (Depth-First Search)
        # Time  complexity: O(N x 2^N) = O(N x 9 x 2^(N-1))
        # Space compleixty: O(2^N) = O(9 x 2^(N-1)) + O(N)
        # if n == 1:
        #     return [i for i in range(10)]

        # ans = []
        # def dfs(n, num):
        #     # base case
        #     if n == 0:
        #         return ans.append(num)

        #     tail_digit = num % 10
        #     # using set() to avoid duplicates when K == 0
        #     next_digits = set([tail_digit + k, tail_digit - k])

        #     for next_digit in next_digits:
        #         if 0 <= next_digit < 10:
        #             new_num = num * 10 + next_digit
        #             dfs(n - 1, new_num)

        # for num in range(1, 10):
        #     dfs(n - 1, num)

        # return list(ans)


        # BFS (Breadth-First Search)
        # Time  complexity: O(N x 2^N)
        # Space complexity: O(2^N)
        if n == 1:
            return [i for i in range(10)]

        # initialize the queue with candidates for the first level
        queue = [digit for digit in range(1, 10)]

        for level in range(n - 1):
            next_queue = []
            for num in queue:
                tail_digit = num % 10
                # using set() to avoid duplicates when K == 0
                next_digits = set([tail_digit + k, tail_digit - k])

                for next_digit in next_digits:
                    if 0 <= next_digit < 10:
                        new_num = num * 10 + next_digit
                        next_queue.append(new_num)

            # start the next level
            queue = next_queue

        return queue


class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:

        if N == 1:
            return [i for i in range(10)]

        # initialize the queue with candidates for the first level
        queue = [digit for digit in range(1, 10)]

        for level in range(N-1):
            next_queue = []
            for num in queue:
                tail_digit = num % 10
                # using set() to avoid duplicates when K == 0
                next_digits = set([tail_digit + K, tail_digit - K])

                for next_digit in next_digits:
                    if 0 <= next_digit < 10: 
                        new_num = num * 10 + next_digit
                        next_queue.append(new_num)
            # start the next level
            queue = next_queue

        return queue

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        if n == 1:
            return list(range(10))
        
        ans = []
        
        for num in range(1, 10):
            self.dfs(n-1, num, ans, k)
        
        return ans
    
    def dfs(self, n, num, ans, k):
        if n == 0:
            return ans.append(num)
        
        last_digit = num % 10
        
        next_ds = set([last_digit + k, last_digit - k])
        
        for digit in next_ds:
            if 0 <= digit < 10:
                tmp = num * 10 + digit
                self.dfs(n-1, tmp, ans, k)



class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        queue=[]
        ans = []
        for i in range(1,10):
            queue.append(str(i))
        while len(queue)>0:
            num = queue.pop(0)
            #print(queue)
            #print(num,len(num))
            if len(num)==n and (num not in ans):
                ans.append(num)

            elif len(num)<n:
                x=int(num[-1])
                if x-k>=0:
                    queue.append(num+str(x-k))
                if x+k<=9:
                    queue.append(num+str(x+k))
        
        #print(queue)
        
        
        return ans
    
    


class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:


        ans = []
        def DFS(N, num):
            # base case
            if N == 0:
                return ans.append(num)

            tail_digit = num % 10
            # using set() to avoid duplicates when K == 0
            next_digits = set([tail_digit + K, tail_digit - K])

            for next_digit in next_digits:
                if 0 <= next_digit < 10: 
                    new_num = num * 10 + next_digit
                    DFS(N-1, new_num)

        for num in range(1, 10):
            DFS(N-1, num)

        return list(ans)

class Solution:
    def numsSameConsecDiff(self, n, k):
        res = []
        for i in range(1, 10):
            neighbors = self.helper(i, k)
            for neighbor in neighbors:
                res.append([i, neighbor])

        if n > 2:
            n -= 2
            while n > 0:
                temp = []
                for sublist in res:
                    neighbors = self.helper(sublist[-1], k)
                    for neighbor in neighbors:
                        temp.append(sublist + [neighbor])
                n -= 1
                res = temp
        for i in range(len(res)):
            res[i] = int(''.join(str(ele) for ele in res[i]))


        return res

    def helper(self, val, k):
        res = set()
        if val + k <= 9:
            res.add(val + k)
        if val - k >= 0:
            res.add(val - k)
        return res

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        
        def dfs(N, K, digit, rst):
            if not N: 
                rst.append(int(''.join(map(str, digit)))); return
            if digit[-1] + K <= 9: 
                dfs(N-1, K, digit + [digit[-1] + K], rst)
            if digit[-1] - K >= 0: 
                dfs(N-1, K, digit + [digit[-1] - K], rst)
        
        if N == 1: return list(range(10))
        if K == 0: return [int(str(i) * N) for i in range(1, 10)]
        rst = []
        for i in range(1, 10):
            dfs(N-1, K, [i], rst)
        return rst


class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def solve(x):
            s = str(x)
            if len(s) > 1 and abs(int(s[-1]) - int(s[-2])) != k:
                return
            if len(s) == n and abs(int(s[-1]) - int(s[-2])) == k:
                result.append(x)
            if len(s) == n:
                return
            for i in range(0, 10):
                solve(x * 10 + i)

        result = []
        for i in range(1, 10):
            solve(i)
        return result


class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        result = {1, 2, 3, 4, 5, 6, 7, 8, 9}
        
        for i in range(1, n):
            temp = list()
            for r in result:
                if k == 0:
                    temp.append(r * 10 + r % 10)
                else:
                    back = r % 10
                    if back - k >= 0:
                        temp.append(r * 10 + back - k)
                    if back + k < 10:
                        temp.append(r * 10 + back + k)
            result = temp.copy()
        
        return result

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        '''
        dp问题: dp[i] = dp[i-1] * 10 + dp[i-1][-1] +/- K.
        其中dp[i-1][-1]代表dp[i-1]的个位数, +/- K代表对K的加减.
        '''
        dp = list(range(10))
        for _ in range(N-1):
            _dp = set()
            for x in dp:
                for y in [x % 10 + K, x % 10 - K]:
                    if x and 0 <= y <= 9:
                        _dp.add(x * 10 + y)
            dp = _dp
        
        return list(dp)


class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        import math
        from collections import deque
        
        deq = deque([i for i in range(1, 10)])
        res = []

        while deq:
            num = deq.popleft()

            if math.pow(10, n-1) <= num < math.pow(10, n): # in n
                res.append(num)
            else:
                targets = [num % 10 - k, num % 10 + k] if k > 0 else [num % 10]
                for target in targets:
                    if 0 <= target <= 9:
                        deq.append(num*10 + target)

        return res


class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:

        if N == 1:
            return [i for i in range(10)]

        ans = []
        def DFS(N, num):
            # base case
            if N == 0:
                return ans.append(num)

            tail_digit = num % 10
            # using set() to avoid duplicates when K == 0
            next_digits = set([tail_digit + K, tail_digit - K])

            for next_digit in next_digits:
                if 0 <= next_digit < 10: 
                    new_num = num * 10 + next_digit
                    DFS(N-1, new_num)

        for num in range(1, 10):
            DFS(N-1, num)

        return list(ans)

import itertools

class Solution:        
    def step(self, n, k):
        d = n % 10
        b = n * 10

        if k == 0:
            yield b + d 
        if d < d + k < 10:
            yield b + d + k
        if 0 <= d - k < d:
            yield b + d - k

    def solve(self, nums, n, k):
        if n == 1:
            return nums
        soln = [self.step(x, k) for x in nums]
        return itertools.chain.from_iterable([self.solve(x, (n - 1), k) for x in soln])

    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        seed = [x for x in range(1, 10) if x + k < 10 or 0 <= x - k < 10]
        return list(self.solve(seed, n, k))


class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        @functools.lru_cache(maxsize=128, typed=False)
        def check(n, k, s):
            #   s表示起点
            rtv = []
            if n == 0:
                return []
            rtv = []
            for i in range(10):
                if abs(i-s)==k:
                    r1 = check(n-1, k, i)
                    if r1:
                        for r in r1:
                            rtv.append([i] + r)
                    else:
                        rtv.append([i])
                    
            return rtv
    
        rtv = []
        for i in range(1, 10):
            r0 = check(n-1, k, i)
            for r in r0:
                t = i
                for c in r:
                    t = t * 10 + c
                rtv.append(t)
        return rtv

class Solution:
    def numsSameConsecDiff(self, n, k):
        d = {}
        for i in range(10):
            temp = set()
            if i + k <= 9:
                temp.add(i + k)
            if i - k >= 0:
                temp.add(i - k)
            d[i] = list(temp)


        res = []
        for i in range(1, 10):
            for neighbor in d[i]:
                res.append([i, neighbor])

        if n > 2:
            n -= 2
            while n > 0:
                temp = []
                for sublist in res:
                    for neighbor in d[sublist[-1]]:
                        temp.append(sublist + [neighbor])
                n -= 1
                res = temp
        for i in range(len(res)):
            res[i] = int(''.join(str(ele) for ele in res[i]))


        return res

class Solution:
    def recurse(self, prev_digit: int, remaining:int, k:int) -> List[List[int]]:
        if remaining == 0:
            raise Exception()
        curr_digits = set(filter(lambda d: d>=0 and d<10, [prev_digit+k, prev_digit-k]))
        ret = []
        for curr_digit in curr_digits:
            if remaining > 1:
                nums = self.recurse(curr_digit, remaining-1, k)
                for num in nums:
                    # print('num', num)
                    new_num = [curr_digit]+num
                    # print('new_num', new_num)
                    ret.append(new_num)
            else:
                ret.append([curr_digit])
        
        # print(prev_digit, ret)
        return ret
    
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        ret = []
        for d in range(1, 10):
            nums = self.recurse(d, n-1, k)
            for num in nums:
                new_num = [d]+num
                ret.append(new_num)
        ret = list(filter(lambda l: len(l)==n, ret))
        ret = list(map(lambda l: [str(c) for c in l], ret))
        return [\"\".join(num) for num in ret]