LeetCode如何輸入字符串的排列

這篇文章主要介紹了LeetCode如何輸入字符串的排列，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

我們提供的服務有：成都做網站、成都網站建設、微信公眾號開發(fā)、網站優(yōu)化、網站認證、太平ssl等。為近1000家企事業(yè)單位解決了網站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的太平網站制作公司

 

題目描述

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

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

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

感謝你能夠認真閱讀完這篇文章，希望小編分享的“LeetCode如何輸入字符串的排列”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯，關注創(chuàng)新互聯行業(yè)資訊頻道，更多相關知識等著你來學習!

新聞標題：LeetCode如何輸入字符串的排列
轉載源于：http://bm7419.com/article28/gijjjp.html

成都網站建設公司_創(chuàng)新互聯，為您提供自適應網站、網站收錄、Google、標簽優(yōu)化、、網站排名

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯

成都網站建設