劍指 Offer 38. 字元串的排列 - leetcode 劍指offer系列

題目難度: 中等

原題連結

今天繼續更新劍指 offer 系列, 這道題又是相當經典, 這裡提供一種非常通用的方法供大家參考, 它還能解決類似的問題, 比如數字的排列, 也不用考慮有重複元素的情況

老樣子晚上 6 點 45 分準時更新公衆号 每日精選算法題, 大家記得關注哦~ 另外在公衆号裡回複 offer 就能看到劍指 offer 系列目前連載的所有文章了

題目描述

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

你可以以任意順序傳回這個字元串數組，但裡面不能有重複元素。

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
           

大家可以在下面這些地方找到我~😊

我的知乎專欄

我的 CSDN

我的 Leetcode

我的牛客網部落格

我的公衆号: 每日精選算法題, 歡迎大家掃碼關注~😊