Compute the Sequential Digits within a Range using DFS, BFS, or

  • 时间：2020-09-13 14:33:25
  • 分类：网络文摘
  • 阅读：155 次

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

Hints:
Generate all numbers with sequential digits and check if they are in the given range.
Fix the starting digit then do a recursion that tries to append all valid digits.

The very brutal solution would be to check each number between [low, high] and test if it qualifies the sequential digits. This will run in O(N) where N is the count of all numbers within in the range. Given the range may be large, this solution is not practical.

A Better Bruteforce Algorithm

A better bruteforce solution will be to list all sequential digits within the range – which is 32-bit signed integers. Searching from the two digits, then third digits so on until the value in the candidate list is larger than the upperbound of the range. The bruteforce complexity is O(1) – so as the space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        all = [12,23,34,45,56,67,78,89,\
                         123,234,345,456,567,678,789,\
                         1234,2345,3456,4567,5678,6789,\
                         12345,23456,34567,45678,56789,\
                         123456,234567,345678,456789,\
                         1234567,2345678,3456789,\
                         12345678,23456789,\
                         123456789]
        res = []
        for i in all:
            if i >= low and i <= high:
                res.append(i)
            if i >= high:
                break
        return res
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        all = [12,23,34,45,56,67,78,89,\
                         123,234,345,456,567,678,789,\
                         1234,2345,3456,4567,5678,6789,\
                         12345,23456,34567,45678,56789,\
                         123456,234567,345678,456789,\
                         1234567,2345678,3456789,\
                         12345678,23456789,\
                         123456789]
        res = []
        for i in all:
            if i >= low and i <= high:
                res.append(i)
            if i >= high:
                break
        return res

Translating to C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> all = {12,23,34,45,56,67,78,89,
                         123,234,345,456,567,678,789,
                         1234,2345,3456,4567,5678,6789,
                         12345,23456,34567,45678,56789,
                         123456,234567,345678,456789,
                         1234567,2345678,3456789,
                         12345678,23456789,
                         123456789};
        vector<int> result;
        for (const auto &n: all) {
            if (n >= low && n <= high) {
                result.push_back(n);
            }
            if (n >= high) break;
        }
        return result;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> all = {12,23,34,45,56,67,78,89,
                         123,234,345,456,567,678,789,
                         1234,2345,3456,4567,5678,6789,
                         12345,23456,34567,45678,56789,
                         123456,234567,345678,456789,
                         1234567,2345678,3456789,
                         12345678,23456789,
                         123456789};
        vector<int> result;
        for (const auto &n: all) {
            if (n >= low && n <= high) {
                result.push_back(n);
            }
            if (n >= high) break;
        }
        return result;
    }
};

Another bruteforce algorithm to generate the sequential digits between the range is to iterate 10 times and start with each possible digit from 1 to 9:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> result;
        for(int i = 1; i < 10; ++ i) {
            int value = 0;
            for(int j = i; j < 10; ++ j) {
                value = value * 10 + j;
                if ((value <= high) && (value >= low)) {
                    result.push_back(value);
                }
            }
        }
        sort(begin(result), end(result));
        return result;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> result;
        for(int i = 1; i < 10; ++ i) {
            int value = 0;
            for(int j = i; j < 10; ++ j) {
                value = value * 10 + j;
                if ((value <= high) && (value >= low)) {
                    result.push_back(value);
                }
            }
        }
        sort(begin(result), end(result));
        return result;
    }
};

This requires sorting the result set. The Python implementation:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        for i in range(1, 10):
            value = 0
            for j in range(i, 10):
                value = value * 10 + j
                if value >= low and value <= high:
                    ans.append(value)
        return sorted(ans)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        for i in range(1, 10):
            value = 0
            for j in range(i, 10):
                value = value * 10 + j
                if value >= low and value <= high:
                    ans.append(value)
        return sorted(ans)

Depth First Search Algorithm

Now, comes to the classic search solution – Depth First Search (DFS). We can start searching at 1 to 9, then each time append a increasing digit if the last digit is not 9. The implementation of DFS is usually based on recursion, which requires maintaining stack calls during runtime – which will be handled by the compiler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        def dfs(x):
            if x >= low and x <= high:
                ans.append(x)
            if x > high:
                return
            y = x % 10
            if y != 9:
                dfs(x * 10 + (y + 1))
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        def dfs(x):
            if x >= low and x <= high:
                ans.append(x)
            if x > high:
                return
            y = x % 10
            if y != 9:
                dfs(x * 10 + (y + 1))
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)

Same DFS algorithm implemented in C++ may look a bit verbose – given the use of vector – appending the result from DFS function to the result vector using the insert method.

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
28
29
30
31
32
33

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++ i) {
            vector<int> v = dfs(low, high, i);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        sort(begin(res), end(res));
        return res;
    }
    
private:
    vector<int> dfs(int low, int high, int cur = 0) {
        vector<int> res;
        if (cur >= low && cur <= high) {
            res.push_back(cur);
        }
        if (cur >= high) {
            return res;
        }
        int x = cur % 10;
        if (x != 9) {
            vector<int> v = dfs(low, high, cur * 10 + x + 1);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        return res;
    }    
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++ i) {
            vector<int> v = dfs(low, high, i);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        sort(begin(res), end(res));
        return res;
    }
    
private:
    vector<int> dfs(int low, int high, int cur = 0) {
        vector<int> res;
        if (cur >= low && cur <= high) {
            res.push_back(cur);
        }
        if (cur >= high) {
            return res;
        }
        int x = cur % 10;
        if (x != 9) {
            vector<int> v = dfs(low, high, cur * 10 + x + 1);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        return res;
    }    
};

Breadth First Search Algorithm

The BFS (Breadth First Search) Algorithm avoids the recursion stacks – by using a queue. The next sequential digits (child nodes) are pushed to the queue after a current number is dequed until the queue becomes empty – which means all solutions have been tried.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        Q = []
        for i in range(1, 10):
            Q.append(i)
        res = []
        while len(Q) > 0:
            p = Q.pop(0)
            if p >= low and p <= high:
                res.append(p)
            x = p % 10            
            if x != 9 and x < high:
                Q.append(p * 10 + x + 1)
        return sorted(res)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        Q = []
        for i in range(1, 10):
            Q.append(i)
        res = []
        while len(Q) > 0:
            p = Q.pop(0)
            if p >= low and p <= high:
                res.append(p)
            x = p % 10            
            if x != 9 and x < high:
                Q.append(p * 10 + x + 1)
        return sorted(res)

Translating to C++:

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

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            int p = Q.front();
            Q.pop();
            if (p >= low && p <= high) {
                res.push_back(p);
            }
            if (p < high) {
                int x = p % 10;
                if (x != 9) {
                    Q.push(p * 10 + x + 1);
                }
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            int p = Q.front();
            Q.pop();
            if (p >= low && p <= high) {
                res.push_back(p);
            }
            if (p < high) {
                int x = p % 10;
                if (x != 9) {
                    Q.push(p * 10 + x + 1);
                }
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};

All these implementations are O(1) in time given the range is restricted to a 32-bit signed integer – thus it takes at most 10 iterations to search the solution space.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
香蕉和橘子能起到解毒护肝的作用　 吃葡萄、喝葡萄酒能帮助调节性功能　 绿茶、红茶、青茶、黑茶、白茶和黄茶　 奶茶多添加奶精 长期食用会引发心脏病　 奶茶调查：街头奶茶店调香味多用奶精　 适合秋天食用的养肺食谱可滋阴润肺　 哪些食物可以起到止咳润肺的作用　 食物的禁忌：中医如何区分食物的寒热性　 味道鲜美营养丰富的黑木耳最佳吃法　 怎样食用萝卜可以治咳嗽使症状缓解　
评论列表
添加评论