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

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

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

推荐阅读：
WordPress Adds Google Translate Widget　 The Ultimate LinkedIn Cheat Sheet　 Amazon Email Scam Has Consumers On High Alert　 Department Of Justice Announces ‘Hack The Army’ Program　 7 Things You Must Do After Installing Your WordPress Site　 New Report Discovers Disconnect Between Retailers And Social Med　 Counting the Prime Arrangements　 The Minimum Absolute Difference Algorithm of an Array　 Implement the Depth First Search Algorithm in Graph using Simple　 Beginner’s Introduction to PHP Memcached　
评论列表
添加评论