1291. Sequential Digits

1291. Sequential Digits (Medium)

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

Related Topics:
Backtracking

Solution 1.

// OJ: https://leetcode.com/problems/sequential-digits/
// Author: github.com/lzl124631x
// Time: O(1) since there are limited number of valid integers
// Space: O(1)
class Solution {
    long get(int start, int len) {
        long ans = 0;
        while (len-- > 0) {
            ans = ans * 10 + start;
            ++start;
        }
        return ans;
    }
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        int len = 0, tmp = len;
        while (tmp) {
            tmp /= 10;
            ++len;
        }
        while (len <= 9) {
            for (int i = 1; i <= 9 - len + 1; ++i) {
                long long n = get(i, len);
                if (n < low) continue;
                if (n > high) return ans;
                ans.push_back(n);
            }
            ++len;
        }
        return ans;
    }
};