[LeetCode] 1291. Sequential Digits

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:

10 <= low <= high <= 10^9

顺次数。题意是给一个下限low和一个上限high，请输出一个有序的list，list里面是所有介于low和high之间的数字，同时数字满足每一位上的数字都比前一位上的数字大 1 。这道题有三种做法。暴力枚举，DFS和BFS。因为数据量的关系，所以这道题我觉得无论是什么做法，时间复杂度都是O(1)，空间复杂度都是O(n)，因为要输出的是一个list。

枚举虽然是暴力，但是由于最后答案本身就不是很多，所以代码也能过。具体的思路是，首先创建一个字符串“123456789”，按位遍历这个字符串，以在指针i上的数字作为开头，并尝试生成后面更大的数字。如果生成的数字大于high了就停止。

 1 class Solution {
 2     public List<Integer> sequentialDigits(int low, int high) {
 3         String s = "123456789";
 4         List<Integer> res = new ArrayList<>();
 5         for (int i = 1; i < 10; i++) {
 6             for (int j = 0; j < s.length() - i + 1; j++) {
 7                 int num = Integer.parseInt(s.substring(j, j + i));
 8                 if (num > high) {
 9                     return res;
10                 }
11                 if (num >= low) {
12                     res.add(num);
13                 }
14             }
15         }
16         return res;
17     }
18 }

DFS的做法也是从1到9开始确定第一位上的数字。同时需要一个变量target记录已经生成的数字，那么下一个要被生成的数字就是target * 10 + start。举例，假设第一位start = 1，此时的target也是1；当遍历到下一层的时候，start = 2，target = 10 + 2 = 12；再下一层的时候，start = 3，target = 120 + 3 = 123。以此类推。

 1 class Solution {
 2     public List<Integer> sequentialDigits(int low, int high) {
 3         List<Integer> res = new ArrayList<>();
 4         for (int i = 1; i <= 9; i++) {
 5             dfs(res, i, 0, low, high);
 6         }
 7         Collections.sort(res);
 8         return res;
 9     }
10 
11     private void dfs(List<Integer> res, int start, int target, int low, int high) {
12         // base case
13         if (target >= low && target <= high) {
14             res.add(target);
15         }
16         if (start > 9 || target > high) {
17             return;
18         }
19         dfs(res, start + 1, target * 10 + start, low, high);
20     }
21 }

BFS的做法跟DFS类似，也是先拿到第一个数字，用queue去筛一遍，如果在范围内就加到结果集。

 1 class Solution {
 2     public List<Integer> sequentialDigits(int low, int high) {
 3         List<Integer> res = new ArrayList<>();
 4         Queue<Integer> queue = new LinkedList<>();
 5         for (int i = 1; i <= 9; i++) {
 6             queue.offer(i);
 7         }
 8         while (!queue.isEmpty()) {
 9             int target = queue.poll();
10             if (target >= low && target <= high) {
11                 res.add(target);
12             }
13             int tail = target % 10;
14             if (tail < 9 && target <= high) {
15                 queue.offer(target * 10 + tail + 1);
16             }
17         }
18         return res;
19     }
20 }

LeetCode 题目总结