검 지 offer 문자열 의 배열 (전체 배열 역 추적, DFS)

묘사 하 다.
문자열 을 입력 하고 이 문자열 의 모든 배열 을 사전 순서에 따라 출력 하 십시오.예 를 들 어 문자열 abc 를 입력 하면 문자 a, b, c 가 배열 할 수 있 는 모든 문자열 abc, acb, bac, bca, cab 와 cba 를 출력 합 니 다.입력 설명: 문자열 을 입력 하 십시오. 길 이 는 9 를 초과 하지 않 습 니 다. (문자 중복 이 있 을 수 있 습 니 다) 문 자 는 대소 문자 만 포함 합 니 다.
솔 루 션 1 교체

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        ans, tmpans = [ss[0]], []
        for i in range(1, len(ss)):
            for item in ans:
                for j in range(len(item)+1):
                    # print(item)
                    tmp = item[:j]+ss[i]+item[j:]
                    if tmp not in tmpans:
                        tmpans.append(tmp)
            ans = tmpans
            tmpans = []
        ans.sort()
        return ans

솔 루 션 2 역 추적
모두 줄 지어 거 슬러 올라가다.

class Solution:
    def Permutation(self, ss):
        n = len(ss)
        res = []
        def helper(s, tmp):
            if tmp and not s and tmp not in res:
                res.append(tmp[:])
            for i in range(len(s)):
                helper(s[:i]+s[i+1:], tmp+s[i])
        helper(ss, '')
        return res

Solution 3 DFS
일반적인 DFS 는 배열 로 돌아 가 다시, 정렬 처 리 를 하 는 것 에 주의 하 십시오.

class Solution:
    def __init__(self):
        self.ss = ''
        self.visited = []
        self.tmpAns = []
        self.ans = []

    def Permutation(self, ss):
        self.ss = ss
        self.visited = [False for _ in self.ss]
        self.tmpAns = [None for _ in self.ss]
        if ss != '':
            self.DFS(0)
        res = [''.join(_) for _ in self.ans]
        res = list(set(res))
        res.sort()
        return res

    def DFS(self, curIndex):
        if curIndex == len(self.ss):
            self.ans.append(self.tmpAns[:])
            # print(self.tmpAns)
            return
        for index in range(len(self.ss)):
            if self.visited[index] == False:
                self.visited[index] = True
                self.tmpAns[curIndex] = self.ss[index]#index       curIndex
                self.DFS(curIndex+1)
                self.visited[index] = False