LeetCode 967. Numbers With Same Consecutive Differences

Posted on | In |
Words count in article: 225 | Reading time ≈ 1

题目

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:

1
2
3
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:

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

Note:

  • 1 <= N <= 9
  • 0 <= K <= 9

思路

DFS.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        if N == 1:
            return [i for i in range(10)]
        global res 
        res = []
        for num in range(1, 10):
            self.dfs(N-1, num, K)
        return list(res)
    
    
    def dfs(self, N, num, K):
        # base case
        if N == 0:
            return res.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
                self.dfs(N-1, new_num, K)