LeetCode 解題筆記：3720. Lexicographically Smallest Permutation Greater Than Target

作者：王一哲
日期：2026年8月27日


LeetCode 題目連結：3720. Lexicographically Smallest Permutation Greater Than Target

解題想法

中等難度題。題目給一個字串 $s$ 及目標字串 $target$，將 $s$ 重新排列成大於 $target$ 之中最小的字串。由於字串的長度最長為 300，如果用 next_permutation 測試所有的排列方式一定會超時，一定要用 dfs 並搭配剪枝才不會超時。整個題目最主要的解題過程在於 dfs 函式，代入的項目有：

1. 目前檢查的 $target$ 索引值 $idx$
2. 目前選取的字串 $path$ 是否已經大於 $target$ 的前綴 is_greater
3. 目前選取的字串 $path$
4. 已經選取的字母索引值 $used$

函式主要分成幾個部分：

1. 已經找到答案，直接回傳 true。
2. 遞迴出口，已經找到最後一位，如果 is_greater 為 true，設定答案 $ans$，回傳 true。
3. 由左到右放入字母，裡面再分成以下的步驟：
   1. 跳過已經選取的字母
   2. 剪枝，跳過重覆且不符合要求的字母。
   3. 剪枝，如果 is_greater == false，不能放入小於 target[idx] 的字母。
   4. 試著放入 ch，如果新的狀態 new_is_greater 為 true，加入剩下的字母就是答案；反之，遞迴，往下走，遞迴完之後再回溯。

Python 程式碼

Runtime: 55 ms, beats 5.26%. Memory: 20.04 MB, beats 11.84%.

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        chars = sorted(s)  # 字母先排序
        ans = ""  # 答案

        # DFS，idx 目前正在比較 target[idx]，is_greater 目前的字串是否大於 target 前綴
        # path 目前的字串，used 已選取字母的索引值
        def dfs(idx, is_greater, path, used):
            nonlocal ans  # 改成 nonlocal 才能修改外部變數
            if ans: return True  # 已經找到答案，提早結束
            # 遞迴出口，idx 等於 n
            if idx == n:
                if is_greater:  # 找到大於目標的字串
                    ans = "".join(path)
                    return True
                return False
            # 由左到右放入字母
            for i in range(n):
                # 跳過已經選取的字母
                if used[i]: continue
                # 剪枝，跳過重覆且不符合條件的字母
                if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue
                # 剪枝，如果目前的字串還沒有大於目標，不能放入比 target[idx] 小的字母
                ch = chars[i]
                if not is_greater and ch < target[idx]: continue
                # 試著加入 ch
                path.append(ch)
                used[i] = True
                new_is_greater = is_greater or (ch > target[idx])
                # 剪枝，如果 new_is_greater == True，只要放入剩下的字母就是答案
                if new_is_greater:
                    for j in range(n):
                        if not used[j]:
                            path.append(chars[j])
                    ans = "".join(path)
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path, used):
                    return True
                # 回溯
                path.pop()
                used[i] = False
            # 預設回傳 False
            return False
        # 呼叫 DFS
        dfs(0, False, [], [False] * n)
        return ans

path 的格式改成字串，速度還是很慢。Runtime: 59 ms, beats 5.26%. Memory: 19.86 MB, beats 14.47%.

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        chars = sorted(s)  # 字母先排序
        ans = ""  # 答案

        # DFS，idx 目前正在比較 target[idx]，is_greater 目前的字串是否大於 target 前綴
        # path 目前的字串，used 已選取字母的索引值
        def dfs(idx, is_greater, path, used):
            nonlocal ans  # 改成 nonlocal 才能修改外部變數
            if ans: return True  # 已經找到答案，提早結束
            # 遞迴出口，idx 等於 n
            if idx == n:
                if is_greater:  # 找到大於目標的字串
                    ans = path
                    return True
                return False
            # 由左到右放入字母
            for i in range(n):
                # 跳過已經選取的字母
                if used[i]: continue
                # 剪枝，跳過重覆且不符合條件的字母
                if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue
                # 剪枝，如果目前的字串還沒有大於目標，不能放入比 target[idx] 小的字母
                ch = chars[i]
                if not is_greater and ch < target[idx]: continue
                # 試著加入 ch
                path += ch
                used[i] = True
                new_is_greater = is_greater or (ch > target[idx])
                # 剪枝，如果 new_is_greater == True，只要放入剩下的字母就是答案
                if new_is_greater:
                    for j in range(n):
                        if not used[j]:
                            path += chars[j]
                    ans = path
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path, used):
                    return True
                # 回溯
                path = path[:-1]
                used[i] = False
            # 預設回傳 False
            return False
        # 呼叫 DFS
        dfs(0, False, "", [False] * n)
        return ans

C++ 程式碼

Runtime: 7 ms, beats 42.04%. Memory: 10.10 MB, beats 68.15%.

class Solution {
public:
    string ans;  // 答案

    bool dfs(int idx, bool is_greater, string& path, vector<bool>& used, const int n, const string& s, const string& target) {
        // 已經找到答案，直接回傳 true
        if (!ans.empty()) return true;
        // 遞迴出口，已經找到最後一位
        if (idx == n) {
            if (is_greater) {
                ans = path;
                return true;
            }
            return false;
        }
        // 由左到右放入字母
        for(int i = 0; i < n; i++) {
            // 跳過已經選取的字母
            if (used[i]) continue;
            // 剪枝，跳過重覆且不符合要求的字母
            if (i > 0 && s[i] == s[i-1] && !used[i-1]) continue;
            // 剪枝，如果 is_greater == false，不能放入小於 target[idx] 的字母
            char ch = s[i];
            if (!is_greater && ch < target[idx]) continue;
            // 試著放入 ch
            path += ch;
            used[i] = true;
            bool new_is_greater = is_greater || (ch > target[idx]);
            // 剪枝，如果 new_is_greater == true，加入剩下的字母就是答案
            if (new_is_greater) {
                for(int j = 0; j < n; j++) {
                    if (!used[j]) path += s[j];
                }
                ans = path;
                return true;
            }
            // 遞迴
            if (dfs(idx + 1, new_is_greater, path, used, n, s, target)) return true;
            // 回溯
            path.pop_back();
            used[i] = false;
        }
        return false;  // 預設回傳 false
    }

    string lexGreaterPermutation(string s, string target) {
        int n = (int)s.size();  // 長度
        sort(s.begin(), s.end());  // 字母要先排序
        vector<bool> used (n, false);  // 字母是否已被選取，全部設定成 false
        string path;  // 已選取的字母
        dfs(0, false, path, used, n, s, target);
        return ans;
    }
};