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)
}
for (int i = lengthLow + 1; i < lengthHigh; i++) {
List<Integer> listWithLength = sequentialDigitsWithLength(i);
for (int num : listWithLength)
}
List<Integer> listHigh = sequentialDigitsWithLength(lengthHigh);
if (lengthLow < lengthHigh) {
for (int num : listHigh) {
if (num <= high)
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++) {
num += inc;
}
return list;
}
}

• // 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;
for (int tmp = low; 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;
}
};

• print("Todo!")