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

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

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) —

推荐阅读：
新食品安全法“史上最严”建立惩罚制度　 适合在夏天吃的既简单又美味的凉拌菜　 薏米与红豆的多种搭配煮法可健脾养血　 好时巧克力1年3上黑榜 违规使用维生素E　 近些年被曝光的大米安全事件一览　 夏日进补：男不离韭，女不离藕之解读　 “僵尸肉”蹿上餐桌拷问食品安全监管　 夏季炒菜时可多放一种调料——花椒　 四种热门食物并没有那么神奇的营养功效　 “养胃饼干”不养胃 消费者起诉徐静蕾代言　
评论列表
添加评论