> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/4.depth-first-search/967.-numbers-with-same-consecutive-differences-m.md).

# 967. Numbers With Same Consecutive Differences (M)

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. For example, `01` has one leading zero and is invalid.

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

 

**Constraints:**

* `2 <= n <= 9`
* `0 <= k <= 9`

### Solution:

**Version 1: DFS**

**Version 2: BFS**

先定下第一位的数字1-9， 再依次BFS 入栈

i.e，(3,4)  --> 1, 14, 141, 147, 1414, 1474

```
class Solution {
    
    private Queue<Integer> queue; 
    private Set<Integer> resultSet; 
    public int[] numsSameConsecDiff(int n, int k) {
        
        if(n <=0) return new int[]{};
        queue = new LinkedList<Integer>();
        resultSet = new HashSet<Integer>();
        
        for(int i = 1; i<= 9; i++)
        {
            bfs(i, n, k);
        }
        
        return resultSet.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public void bfs(int firstDigit, int n, int k)
    {
        queue.offer(firstDigit);
        int step = 1;
        while(!queue.isEmpty() && step <=n )
        {
            int size = queue.size();
            for(int i = 0;i< size; i++)
            {
                Integer current = queue.poll();
                /*if(Math.log10(current.intValue())+1 == n)
                {
                    resultSet.add(current);
                }*/
                if(String.valueOf(current).length() == n)
                {
                    resultSet.add(current);
                    continue;
                }
                if(current%10 + k <= 9)
                {
                    queue.offer(current*10+current%10+k);
                }
                if(current%10 - k >= 0)
                {
                    queue.offer(current*10+current%10-k);
                }
            }
            step++;
        }
    }  
}
```