4 min read leetcode

1291. Sequential Digits

1291. Sequential Digits
Photo by Markus Spiske / Unsplash

題目連結：1291. Sequential Digits

題目描述

給定一個範圍 [low, high]，請找出所有介於 low 與 high 之間的「順序數字（Sequential Digits）」並由小到大排序後返回。
「順序數字」是指其每個位數的數字皆為連續遞增的整數，如 123、789、1234 等。

範例

  • 輸入：low = 100, high = 300
    輸出：[123, 234]
    解釋：
    123、234 介於 100 與 300 之間，且皆為連續遞增的數字序列。

限制條件

  • 10 <= low <= high <= 10^9

解題思路

此題的關鍵在於如何高效地生成「順序數字」並篩選出落在 [low, high] 範圍內的數字。由於「順序數字」的結構嚴謹（每位數字嚴格遞增且連續），其總量非常有限。我們可以利用此特性，從小到大生成所有可能的順序數字，再過濾出範圍內的結果。

以下有多種方法實作：

方法一：由小到大枚舉生成（Brute Force Enumeration）

  1. 從 1 到 9 每個數字為起點，嘗試往後接連更大一位數字形成順序數字。
    • 例如，從 1 開始產生：12, 123, 1234, ...，直到無法再插入更大數字或已超過 high。
    • 對於每次生成的數字，如果落在 [low, high] 區間，就將其加入結果。
  2. 最終將結果排序並輸出。

程式碼範例：

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;

        for (int i = 1; i <= 9; i += 1) {
            int num = i;
            int digit = i + 1;
            while (num <= high && digit <= 9) {
                num = num * 10 + digit;
                if (low <= num && num <= high) {
                    ans.push_back(num);
                }
                digit += 1;
            }
        }
        sort(ans.begin(), ans.end());

        return ans;
    }
};

複雜度分析

  • 時間複雜度：O(N)，N為實際生成的順序數字個數。由於每條序列最長不會超過 9 位數，整體可視為常數級別。
  • 空間複雜度：O(N)，用於存放結果。

Refactor version - by @kevinptt0323

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        for (int i = 1; i <= 9; i += 1) {
            for (int num = i, digit = i; num <= high && digit <= 9;
                digit += 1, num = num * 10 + digit) {
                if (num >= low) {
                    ans.push_back(num);
                }
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

方法二：利用字串處理（String Approach）

  1. 定義字串 s = "123456789"。
  2. 分別計算 low 與 high 的位數長度 lenMin 和 lenMax。
  3. 對於長度 i 從 lenMin 到 lenMax：
    • 使用 s 的長度為 i 的子字串來生成對應的數字，檢查是否落在 [low, high] 範圍內。

程式碼範例：

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;

        string s = "123456789";

        int lenMin = to_string(low).size();
        int lenMax = to_string(high).size();
        for (int i = lenMin; i <= lenMax; i += 1) {
            for (int j = 0; j < 10 - i; j += 1) {
                int num = stoi(s.substr(j, i));
                if (low <= num && num <= high) {
                    ans.push_back(num);
                }
            }
        }

        return ans;
    }
};

複雜度分析

  • 時間複雜度：O((lenMax - lenMin + 1) * 9)，對每個長度進行最多 9 次嘗試。
  • 空間複雜度：O(1)，僅使用少量變數。

方法三：事先預存所有順序數字（Tabulation）

由於所有「順序數字」是可枚舉且數量有限，我們可預先定義一個固定陣列，存放所有可能的順序數字（從最小到最大依序排列）。在程式中，只需遍歷該陣列篩選出 [low, high] 區間的數字即可。

固定陣列範例：

const int tbl[36] = {
    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
};

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;

        for (int i = 0; i < 36; i += 1) {
            if (low <= tbl[i] && tbl[i] <= high) {
                ans.push_back(tbl[i]);
            }
        }

        return ans;
    }
};

複雜度分析

  • 時間複雜度：O(1)，因為陣列為固定大小（36 個元素），遍歷時間是常數級別。
  • 空間複雜度：O(1)，使用固定大小的陣列。

Justin