Java에서 문자열의 모든 순열을 찾는 방법

이 튜토리얼에서는 Java 프로그램에서 문자열의 순열을 찾는 방법을 배우게 될 것입니다. 이것은 tricky한 질문이며 주로 Java 인터뷰에서 물립니다.

Java에서 문자열의 순열에 대한 알고리즘

우리는 먼저 문자열에서 첫 번째 문자를 가져와 나머지 문자와 순열을 만들 것입니다. 문자열이 “ABC”이면 첫 번째 문자는 A이고 나머지 문자의 순열은 BC와 CB입니다. 이제 순열에서 첫 번째 문자를 사용 가능한 위치에 삽입할 수 있습니다. BC -> ABC, BAC, BCA CB -> ACB, CAB, CBA 우리는 순열을 반환하는 재귀 함수를 작성하고 나서 다른 함수를 작성하여 완전한 순열 목록을 얻기 위해 첫 문자를 삽입할 수 있습니다.

문자열의 순열을 출력하는 Java 프로그램

package com.journaldev.java.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find all permutations of a String
 * @author Pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set permutationFinder(String str) {
        Set perm = new HashSet();
        //오류 시나리오 처리
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }

    public static void main(String[] args) {
        String s = "AAC";
        String s1 = "ABC";
        String s2 = "ABCD";
        System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s));
        System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
        System.out.println("\nPermutations for " + s2 + " are: \n" + permutationFinder(s2));
    }
}

I have used Set to store the string permutations. So that duplicates are removed automatically.

출력

Permutations for AAC are: 
[AAC, ACA, CAA]

Permutations for ABC are: 
[ACB, ABC, BCA, CBA, CAB, BAC]

Permutations for ABCD are: 
[DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]

Java에서 문자열의 모든 순열을 찾는 것에 대한 설명은 여기까지입니다.

당신은 우리의 GitHub 저장소에서 예제 프로그램 코드를 다운로드할 수 있습니다.