검 지 offer 2 판 - 38. 문자열 의 배열

본 시리즈 내 비게 이 션: 검 지 offer (제2판) java 내 비게 이 션 실현 첩] (http://www.jianshu.com/p/010410a4d419)
면접 문제 38: 문자열 의 배열
제목 요구: 문자열 을 입력 하여 이 문자열 의 모든 배열 을 출력 합 니 다.abc 를 입력 하면 abc, acb, bac, bca, cab, cba 를 인쇄 합 니 다.
문제 풀이 사고: 배열 과 조합 은 수학 적 으로 흔히 볼 수 있 는 문제 이다.문제 풀이 방향 은 수학 적 으로 총 수 를 배열 하 는 것 과 유사 하 다. 먼저 첫 번 째 위치의 요 소 를 확정 한 다음 에 한 번 에 모든 위 치 를 확정 하고 모든 위치 가 확실 할 때 모든 상황 을 완전히 나열 하면 된다.abc 의 경우 저 는 세 개의 빈 공간 을 설정 한 다음 에 abc 의 요 소 를 선택 하여 상기 공중 에 넣 는 것 에 익숙 했 습 니 다.한편, 책 에서 주 는 사고방식 은 교환 을 통 해 여러 가지 가능 한 배열 을 얻 는 것 이다. 구체 적 인 사고방식 은 다음 과 같다.

  a,b,c（   0,1,2）
0 0  , a,b,c => 1 1  , a,b,c =>2 2  , a,b,c(  )
                => 1 2  ， a,c,b =>2 2  , a,c.b(  )
0 1  , b,a,c => 1 1  , b,a,c =>2 2  , b,a,c(  )
                => 1 2  ， b,c,a =>2 2  , b,c,a(  )
0 2  , c,b,a => 1 1  , c,b,a =>2 2  , c,b,a(  )
                => 1 2  ， c,a,b =>2 2  , c,a.b(  )

책 에서 해법 은 문자 가 중복 되 는 문 제 를 고려 하지 않 았 다.중복 문자 가 있 는 경우, 예 를 들 어 a, a, b, 교환 0, 1 호 요 소 는 전후 에 변화 가 없다. 즉, 생 성 된 서열 결 과 를 보면 같은 배열 이기 때문에 중복 문자 에 대해 교환 하지 않 으 면 된다. 사고방식 은 다음 과 같다.

  a,a,b（   0,1,2）
0 0  , a,a,b => 1 1  , a,a,b =>2 2  , a,a,b(  )
                => 1 2  ， a,b,a =>2 2  , a,b,a(  )
0 1  ,  
0 2  , b,a,a =>1 1  , b,a,a =>2 2  , b,a,a(  )
                =>1 2  ，  

문자 중복 해법 의 실현 을 고려 하면 다음 과 같다.

package chapter4;

import java.util.*;

/**
 * Created by ryder on 2017/7/22.
 *       
 */
public class P197_StringPermutation {
    public static List permutation(char[] strs) {
        if (strs == null || strs.length == 0)
            return null;
        List ret = new LinkedList<>();
        permutationCore(strs, ret, 0);
        return ret;
    }
    //   bound      [bound,length)     ，       ，          。
    // a,b,c
    //0 0  , a,b,c => 1 1  , a,b,c =>2 2  , a,b,c(  )
    //                => 1 2  ， a,c,b =>2 2  , a,c.b(  )
    //0 1  , b,a,c => 1 1  , b,a,c =>2 2  , b,a,c(  )
    //                => 1 2  ， b,c,a =>2 2  , b,c,a(  )
    //0 2  , c,b,a => 1 1  , c,b,a =>2 2  , c,b,a(  )
    //                => 1 2  ， c,a,b =>2 2  , c,a.b(  )

    // a,a,b
    //0 0  , a,a,b => 1 1  , a,a,b =>2 2  , a,a,b(  )
    //                => 1 2  ， a,b,a =>2 2  , a,b,a(  )
    //0 1  ,  
    //0 2  , b,a,a =>2 2  ， b,a,a(  )
    public static void permutationCore(char[] strs, List ret, int bound) {
        if (bound == strs.length)
            ret.add(Arrays.copyOf(strs, strs.length));
        Set set = new HashSet<>();
        for (int i = bound; i < strs.length; i++) {
            if (set.add(strs[i])) {
                swap(strs, bound, i);
                permutationCore(strs, ret, bound + 1);
                swap(strs, bound, i);
            }
        }
    }

    public static void swap(char[] strs, int x, int y) {
        char temp = strs[x];
        strs[x] = strs[y];
        strs[y] = temp;
    }

    public static void main(String[] args) {
        char[] strs = {'a', 'b', 'c'};
        List ret = permutation(strs);
        for (char[] item : ret) {
            for (int i = 0; i < item.length; i++)
                System.out.print(item[i]);
            System.out.println();
        }
        System.out.println();
        char[] strs2 = {'a', 'a', 'b','b'};
        List ret2 = permutation(strs2);
        for (char[] item : ret2) {
            for (int i = 0; i < item.length; i++)
                System.out.print(item[i]);
            System.out.println();
        }
    }
}

실행 결과

abc
acb
bac
bca
cba
cab

aabb
abab
abba
baab
baba
bbaa