# [LeetCode] 967. Numbers With Same Consecutive Differences (Medium)

###### tags: `LeetCode`

這題是 2022 年 9 月 3 日的每日任務，我在寫的時候很努力的沒看解答，還好最後有想出來。因為這是解答文，所以就不防雷啦，官方解答給了兩種解法，分別是DFS和BFS。然而，這題事實上不用想得那麼複雜，不需要有關於graph的知識也想得出來（雖然在概念上是相同的）。

## 題目
給定兩個兩個正整數 $n$ 和 $k$，回傳所有長度為 $n$，並且相鄰的數字都相差 $k$ 的整數，並且開頭不能為 0。順序不拘。

## 限制條件
* `2 <= n <= 9`
* `0 <= k <= 9`

## 範例

* Example 1:

    Input: n = 3, k = 7
    Output: [181,292,707,818,929]

注意`070`不是一個有效的答案，因為它的開頭是`0`。

* 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]

## 解答
我做的第一件事，是建立一個字典`candidates`，其中對於每個`0`到`9`的整數`i`，`candidates[i]`包含了和`i`相差`k`，而且同時小於`10`又不小於`0`的整數：

candidates = {}
for i in range(10):
    candidates[i] = []
    if k != 0:
        if i + k < 10:
            candidates[i].append(i + k)
        if i - k >= 0:
            candidates[i].append(i - k)
    else:
        candidates[i].append(i)

接著，我建立了一個`queue`，並初始化為一個包含有 9 個只有單一元素的清單的清單（list of lists），而這9個元素分別為1到9的整數，代表的是候選答案的起始數字：

queue = [[i] for i in range(1, 10)]

這邊我選用queue而不是stack的原因是我一開始想要按照順序把解答建立出來，但後來發現其實只要條件判斷式有設好，用stack也是可以的（queue對應的是官方解答中的BFS，而stack對應的是DFS），只是順序略有不同，但題目並不要求我們排序這些整數。使用python實測發現使用stack和queue在leetcode上並沒有顯著的效能差異。

接下來就是對queue的標準操作。我們 deque（這邊使用`queue.pop(0)`）出需要的元素，對元素進行一些處理，如果滿足條件就加到答案中，不滿足則再塞到queue進行處理
或捨棄：

answer = []
while queue:
    curr = queue.pop(0)
    for c in candidates[curr[-1]]:
        if len(curr + [c]) == n:
            answer.append(int_build(curr + [c]))
        else:
            queue.append(curr + [c])

在這邊我們處理的統一都是整數的list，最後再使用一個`int_build`函式把這些整數concat起來，再轉成整數用來回傳。

完整的code如下：

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def int_build(lst):
            result_str = ""
            for c in lst:
                result_str += str(c)                
            return int(result_str)    
        candidates = {}
        for i in range(10):
            candidates[i] = []
            if k != 0:
                if i + k < 10:
                    candidates[i].append(i + k)
                if i - k >= 0:
                    candidates[i].append(i - k)
            else:
                candidates[i].append(i)
        queue = [[i] for i in range(1, 10)]
        answer = []
        while queue:
            curr = queue.pop()
            for c in candidates[curr[-1]]:
                if len(curr + [c]) == n:
                    answer.append(int_build(curr + [c]))
                else:
                    queue.append(curr + [c])
        return answer