1291. Sequential Digits

題意

題目連結：1291. Sequential Digits

找出所有在範圍 [low, high] 內的「順序數字」。「順序數字」指的是每個數字的數位是遞增且相鄰的，例如 123、456 等

約束條件

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

解題思路

Brute force

要解決這個問題，我們可以利用暴力搜尋的方法來生成所有可能的順序數字，並篩選出符合範圍 [low, high] 的數字。具體步驟如下：

1. 初始化一個空的結果集 ans 用於存儲符合條件的順序數字。
2. 從 1 到 9 的每個數字開始，生成順序數字：
   • 將當前數字存儲在變量 num 中。
   • 將下一個數字存儲在變量 digit 中。
   • 迴圈生成順序數字，直到 num 超過 high 或 digit 超過 9：
     • 將 digit 加入 num 的末尾生成新的順序數字。
     • 如果新的數字在範圍 [low, high] 內，則將其加入結果集 ans。
     • 將 digit 加一，繼續生成下一個順序數字。
3. 將結果集 ans 進行排序，並返回

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 * M)，其中 N 是外層迴圈次數（9 次），M 是內層迴圈次數（取決於 high 和 digit）。
• 空間複雜度：O(1)

---

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

1. 初始化一個空的結果集 ans 用於存儲符合條件的順序數字。
2. 定義一個包含數位 1 到 9 的字符串 s。
3. 計算 low 和 high 的數位長度 lenMin 和 lenMax。
4. 針對每一個長度從 lenMin 到 lenMax 的數字：
   • 透過字符串 s 的子串生成順序數字。
   • 檢查生成的數字是否在範圍 [low, high] 內，如果是則將其加入結果集 ans。
5. 返回結果集 ans

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)，其中 lenMax 和 lenMin 分別是 high 和 low 的數位長度
• 空間複雜度：O(1)

Tabulation

• 預先定義一個常數數組 tbl，其中包含所有可能的順序數字
• 遍歷 tbl 中的所有數字，將符合條件的數字加入結果集 ans 中
• 返回結果集 ans

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)，因為我們只需遍歷固定大小的陣列
• 空間複雜度：O(1)