검지 offer 제2판(Python3)-면접문제 38: 문자열의 배열

제2장 면접에 필요한 기초 지식

제3장 고품질 코드

제4장 면접 문제 해결의 사고방식

면접 문제 27: 두 갈래 나무의 거울

면접 문제 29: 시계 방향 인쇄 매트릭스

면접 문제 30:min 함수를 포함하는 창고

면접 문제 31: 창고의 압입, 팝업 서열

면접 문제

면접 문제 33: 두 갈래 검색 트리의 뒷순서 반복 서열

면접 문제 34: 두 갈래 나무와 어떤 값의 경로

면접 문제

면접 문제 36: 두 갈래 검색 트리와 양방향 체인 테이블

면접 문제 38: 문자열의 배열

제5장 시간과 공간 효율 최적화

제6장 면접에서의 각종 능력

제7장 두 가지 면접 사례

제목 설명    문자열을 입력하고 사전순으로 문자열의 모든 배열을 출력합니다.예를 들어 문자열 abc를 입력하면 문자 a, b, c가 배열할 수 있는 모든 문자열 abc, acb,bac,bca,cab와 cba를 출력합니다.
문제 풀이 사고방식은 두 단계로 나뉜다.

첫 번째 위치에 나타날 수 있는 모든 문자를 구하는 첫 번째 단계

두 번째 단계는 첫 번째 문자를 고정하고 뒤에 있는 모든 문자의 배열을 구한다

뒤에 있는 모든 문자의 배열을 구할 때 귀속을 사용할 수 있습니다.뒤에 있는 모든 문자를 두 부분으로 나눈다. 뒤에 있는 문자의 첫 번째 문자와 이 문자의 뒤에 있는 모든 문자를 나누어 앞의 두 가지 방법을 사용하면 된다.
abc를 예로 들면: a를 고정하고 bc를 남긴다.bc에 b를 고정하고 나머지 c;고정 c, 나머지 b;그래서 bc의 배열은 bc, cb 두 가지가 있다.그래서 a가 1위일 때 abc,acb 두 가지가 있습니다.
동리 b가 1위일 때bac,bca 두 가지가 있다.c가 1위일 때 cba,cab 두 가지가 있습니다.
실전

def Permutation(ss):
    # write code here
    if not ss:
        return []

    def recc(beg, string):
        if beg == len(string) - 1:
            res.add(''.join(string))
        for i in range(beg, len(string)):
            string[i], string[beg] = string[beg], string[i]
            recc(beg + 1, string)
            string[i], string[beg] = string[beg], string[i]

    res = set()
    recc(0, list(ss))
    return sorted(list(res))

두 번째 쓰기 방법:

class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        
        def recc(string, s):
            if not string:
                res.add(s)
            for i in range(len(string)):
                recc(string[:i]+string[i+1:], s+string[i])
            
        res = set()
        recc(ss, '')
        return sorted(list(res))

확장:    문자열의 조합.  abc의 조합은 a, b, c, ab, ac, abc가 있다.ab와 ba는 같은 조합이고 다른 배열이다.
실전

def Permutation(ss):
    # write code here
    if not ss:
        return []

    def recc(string, s):
        if s:
            res.add(s)
        for i in range(len(string)):
            recc(string[i+1:], s + string[i])

    res = set()
    recc(ss, '')
    return sorted(list(res))