Java에서 문자열의 모든 순열을 찾는 방법
이 자습서에서는 Java 프로그램에서 문자열의 순열을 찾는 방법을 배웁니다. 까다로운 질문이며 주로 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<String> permutationFinder(String str) {
Set<String> perm = new HashSet<String>();
//Handling error scenarios
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<String> 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));
}
}
Set을 사용하여 문자열 순열을 저장했습니다. 중복이 자동으로 제거되도록 합니다.
산출
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 리포지토리에서 예제 프로그램 코드를 다운로드할 수 있습니다.