LeetCode 1291: Sequential Digits (Length Enumeration + Sliding Start Digit)
LeetCode 1291EnumerationMathToday we solve LeetCode 1291 - Sequential Digits.
Source: https://leetcode.com/problems/sequential-digits/
English
Problem Summary
Given two integers low and high, return all integers in this interval where every digit is exactly one greater than the previous digit (for example, 1234, 4567).
Key Insight
A sequential-digit number is completely determined by two values:
1) Its length len.
2) Its starting digit start.
Then the number is start, start+1, ..., start+len-1. So we can enumerate all valid (len, start) pairs and keep those in range.
Brute Force and Limitations
Checking every number from low to high is unnecessary and slow for large ranges. Most numbers are not sequential digits. Direct construction is far cleaner and effectively constant-time.
Optimal Algorithm Steps
1) Compute digit lengths of low and high.
2) For each length len in that range:
- valid start digits are 1 to 10-len.
3) Build number by appending digits start..start+len-1.
4) If low <= num && num <= high, add to answer.
5) Enumeration order already gives ascending output.
Complexity Analysis
At most 36 candidates are generated (length 2..9).
Time: O(1) in practice.
Space: O(1) extra (excluding output list).
Common Pitfalls
- Wrong upper bound for start digit (must be 10-len).
- Forgetting to include both boundaries low and high.
- Sorting output unnecessarily (generation order is already sorted).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> ans = new ArrayList<>();
int minLen = String.valueOf(low).length();
int maxLen = String.valueOf(high).length();
for (int len = minLen; len <= maxLen; len++) {
for (int start = 1; start <= 10 - len; start++) {
int num = 0;
for (int d = start; d < start + len; d++) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.add(num);
}
}
}
return ans;
}
}func sequentialDigits(low int, high int) []int {
ans := []int{}
minLen := len(strconv.Itoa(low))
maxLen := len(strconv.Itoa(high))
for l := minLen; l <= maxLen; l++ {
for start := 1; start <= 10-l; start++ {
num := 0
for d := start; d < start+l; d++ {
num = num*10 + d
}
if num >= low && num <= high {
ans = append(ans, num)
}
}
}
return ans
}class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
int minLen = to_string(low).size();
int maxLen = to_string(high).size();
for (int len = minLen; len <= maxLen; ++len) {
for (int start = 1; start <= 10 - len; ++start) {
int num = 0;
for (int d = start; d < start + len; ++d) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.push_back(num);
}
}
}
return ans;
}
};from typing import List
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
ans = []
min_len = len(str(low))
max_len = len(str(high))
for length in range(min_len, max_len + 1):
for start in range(1, 10 - length + 1):
num = 0
for d in range(start, start + length):
num = num * 10 + d
if low <= num <= high:
ans.append(num)
return ansvar sequentialDigits = function(low, high) {
const ans = [];
const minLen = String(low).length;
const maxLen = String(high).length;
for (let len = minLen; len <= maxLen; len++) {
for (let start = 1; start <= 10 - len; start++) {
let num = 0;
for (let d = start; d < start + len; d++) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.push(num);
}
}
}
return ans;
};中文
题目概述
给定区间 [low, high]，返回所有“顺次数”（每一位都比前一位大 1），例如 123、4567。
核心思路
一个顺次数由两个参数唯一确定：
1）长度 len。
2）起始数字 start。
数字就是 start, start+1, ..., start+len-1。因此直接枚举长度和起始位即可，不需要遍历整个区间。
暴力解法与不足
如果从 low 到 high 每个数都判断是否顺次，虽然能做但浪费很大，因为绝大多数数字都不满足条件。构造法更直接、更稳定。
最优算法步骤
1）计算 low 和 high 的位数范围。
2）固定长度 len 后，起始数字只能是 1..10-len。
3）按位拼接得到候选数字。
4）若候选数字在 [low, high] 内，加入答案。
5）由于按长度和起始位升序生成，结果天然有序。
复杂度分析
候选总数最多 36 个（长度 2..9）。
时间复杂度：O(1)（常数级枚举）。
空间复杂度：O(1)（不计输出）。
常见陷阱
- 起始位上界写错：必须是 10-len。
- 忘记区间两端是包含关系。
- 先生成再排序（其实无需排序）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> ans = new ArrayList<>();
int minLen = String.valueOf(low).length();
int maxLen = String.valueOf(high).length();
for (int len = minLen; len <= maxLen; len++) {
for (int start = 1; start <= 10 - len; start++) {
int num = 0;
for (int d = start; d < start + len; d++) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.add(num);
}
}
}
return ans;
}
}func sequentialDigits(low int, high int) []int {
ans := []int{}
minLen := len(strconv.Itoa(low))
maxLen := len(strconv.Itoa(high))
for l := minLen; l <= maxLen; l++ {
for start := 1; start <= 10-l; start++ {
num := 0
for d := start; d < start+l; d++ {
num = num*10 + d
}
if num >= low && num <= high {
ans = append(ans, num)
}
}
}
return ans
}class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
int minLen = to_string(low).size();
int maxLen = to_string(high).size();
for (int len = minLen; len <= maxLen; ++len) {
for (int start = 1; start <= 10 - len; ++start) {
int num = 0;
for (int d = start; d < start + len; ++d) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.push_back(num);
}
}
}
return ans;
}
};from typing import List
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
ans = []
min_len = len(str(low))
max_len = len(str(high))
for length in range(min_len, max_len + 1):
for start in range(1, 10 - length + 1):
num = 0
for d in range(start, start + length):
num = num * 10 + d
if low <= num <= high:
ans.append(num)
return ansvar sequentialDigits = function(low, high) {
const ans = [];
const minLen = String(low).length;
const maxLen = String(high).length;
for (let len = minLen; len <= maxLen; len++) {
for (let start = 1; start <= 10 - len; start++) {
let num = 0;
for (let d = start; d < start + len; d++) {
num = num * 10 + d;
}
if (num >= low && num <= high) {
ans.push(num);
}
}
}
return ans;
};
Comments