Formatted question description: https://leetcode.ca/all/1291.html

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/

// 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;
    }
};

Java

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        if (high == 1000000000)
            high--;
        List<Integer> list = new ArrayList<Integer>();
        int lengthLow = String.valueOf(low).length(), lengthHigh = String.valueOf(high).length();
        List<Integer> listLow = sequentialDigitsWithLength(lengthLow);
        for (int num : listLow) {
            if (num > high)
                break;
            if (num >= low)
                list.add(num);
        }
        for (int i = lengthLow + 1; i < lengthHigh; i++) {
            List<Integer> listWithLength = sequentialDigitsWithLength(i);
            for (int num : listWithLength)
                list.add(num);
        }
        List<Integer> listHigh = sequentialDigitsWithLength(lengthHigh);
        if (lengthLow < lengthHigh) {
            for (int num : listHigh) {
                if (num <= high)
                    list.add(num);
                else
                    break;
            }
        }
        return list;
    }

    public List<Integer> sequentialDigitsWithLength(int length) {
        List<Integer> list = new ArrayList<Integer>();
        int begin = 1, end = 9 - length + 1;
        int num = 0;
        int inc = 0;
        int digit = 1;
        while (digit <= length) {
            num *= 10;
            num += digit;
            digit++;
            inc *= 10;
            inc++;
        }
        for (int i = begin; i <= end; i++) {
            list.add(num);
            num += inc;
        }
        return list;
    }
}

All Problems

All Solutions