剣指offer:Python文字列の配列多様な方法で全配列を実現

目次を読む

タイトル説明

構想及びPython実現

考え方一:再帰書き方

構想二:辞書シーケンスアルゴリズム

タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
構想とPython実現
考え方1:再帰的な書き方
再帰の書き方1

class Solution:
    def Permutation(self, ss):
        # write code here
        list = []
        if len(ss) <= 1:
            return ss
        left = ss[0]
        right = self.Permutation(ss[1:])
        for word in right:
            for i in range(len(word) + 1):
                if word[:i] + left + word[i:] not in list:  #   
                    list.append(word[:i] + left + word[i:])
        list.sort()  #       
        return list

構想2:辞書順アルゴリズム

class Solution:
    def Permutation(self, ss):
        res = []
        if ss == "":
            return res
        if len(ss) == 1:
            return [ss]
        strlist = []
        for i in range(len(ss)):
            strlist.append(ss[i])
        strlist.sort()
        res.append("".join(strlist))
        size = len(strlist)
        while True:
            p = size - 1
            while p >= 1 and strlist[p - 1] >= strlist[p]:
                p -= 1
            if p == 0:
                break
            q = p
            p -= 1
            while q < size and strlist[q] > strlist[p]:
                q += 1
            q -= 1
            self.swap(strlist, p, q)
            self.reverse(strlist, p + 1, size - 1)
            res.append("".join(strlist))
        return res

    def swap(self, strlist, p, q):
        strlist[p], strlist[q] = strlist[q], strlist[p]

    def reverse(self, array, i, j):  #       
        if array is None or i < 0 or j < 0 or i >= j or len(array) < j + 1:
            return
        while i < j:
            self.swap(array, i, j)
            i += 1
            j -= 1