題目描述

輸入一個字符串，打印出該字符串中字符的所有排列。

你可以以任意順序返回這個字符串數組，但里面不能有重復元素。

1 <= s 的長度 <= 8

題目樣例

示例

輸入：s = "abc" 輸出：["abc","acb","bac","bca","cab","cba"]

題目思考

1. 如何不重復地得到所有排列?

解決方案

思路

• 要想不重復地得到所有排列, 我們可以定義一個方法, 來求字典序的下一個排列, 正如題目示例中的輸出數組的順序那樣
• 初始化為最小的字典序, 然后當遍歷到最大的字典序的時候, 就說明所有排列都被找到了
• 所以算法的核心就是如何通過一個字符串找它的字典序的下一個排列
• 下一個排列一定是所有排列中大于當前字符串且最接近它的, 所以我們可以利用貪心算法, 具體步驟如下:
1. 從后向前找第一個                 小于后一個字符的字符 i (因為如果大于等于后一個字符的話, 就沒法與后面的字符交換來使得整體字符串更大了)
2. 找剛才遍歷的部分的大于且最接近 i 的字符 j
3. 將它們兩個互換
4. 然后 i 往后的部分都按字典序從小到大排列
• 這樣就保證了新的字符串一定是大于當前字符串且最接近它的, 不可能有更小的了
• 下面的代碼中有詳細的注釋, 方便大家理解

復雜度

• 時間復雜度 O(N*N!)
• 最差情況下 N 個字符各不相同, 排列就有                 N! 種, 從當前字符串轉入下一個字符串最壞情況下需要                 O(N) 時間
• 空間復雜度 O(1)
• 只使用了幾個變量 (不考慮輸出結果集)

代碼

class Solution:
    def permutation(self, s: str) -> List[str]:
        res = []

        def getNext(s):
            for i in range(len(s) - 1)[::-1]:
                # 從后向前查找
                if s[i] < s[i + 1]:
                    # 找到目標字符了, 接下來找后面部分中大于s[i]且最接近它的字符
                    j = i + 1
                    while j < len(s) and s[j] > s[i]:
                        j += 1
                    # s[j-1]就是后面部分中大于s[i]且最接近它的字符
                    j -= 1
                    # 單獨拿出右邊部分, 肯定嚴格按照降序排列
                    right = s[i + 1:j] + s[i] + s[j + 1:]
                    # 交換字符后, 并加上右邊的翻轉部分(增序, 最小字典序), 就是下一個字典序的字符串
                    return s[0:i] + s[j] + right[::-1]
            # 沒找到下一個字符串, 說明當前字符串就是字典序最大的了, 直接返回None
            return None

        # 先拿到字典序最小的字符串
        s = ''.join(sorted(s))
        while s is not None:
            res.append(s)
            s = getNext(s)
        return res