[LeetCode] 967. Numbers With Same Consecutive Differences

967. Numbers With Same Consecutive Differences

Medium

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

 

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]

 

Constraints:

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

---

문제 풀이

• n 은 숫자의 길이를 나타낸다. 
• k 는 각 정답 숫자 자리의 가능한 차이 값이다. 
• n 길이의 숫자들을 생성할때, 각 자리의 차 값이 k 인 값들을 구해야한다.
• 단 0 으로 시작하여 성립이 될 수 없는 숫자는 제외한다. 
• 숫자를 1 부터 10 까지 선택할 수 있고, n 만큼 숫자 자릿 수를 선택하는 재귀 함수를 만든다.
• 브랜치는 10개, 내려가는 깊이 Level 은 n 까지이다. 
• 가지치기를 고려할때 성립이 될 수 없는 숫자는 0 으로 시작하지 않는 숫자이다.
• 맨 앞 숫자가 0 일때 가지치기가 진행되면, 언제 어디서든 0 이 선택 되도 상관 없다. 
• 그리고 숫자 자리가 첫번째 자리보다 뒤일때, 현재와 이전 자리의 숫자 차이를 비교해서 k 만큼 차이 나지 않으면 가치를 쳐준다.

소스 코드

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        self.ans = []
        self.path = [0] * n
        def rec(lv):
            if lv == n:
                self.ans.append(''.join(map(str,self.path)))
                return
            
            for i in range(0, 10):
                self.path[lv] = i
                if lv == 0 and i == 0:
                    continue
                if lv >= 1 and abs(self.path[lv - 1] - self.path[lv]) != k:
                    continue
                
                rec(lv + 1)
        rec(0)
        return self.ans