「Javaで文字列のすべての組み合わせを見つける方法」

このチュートリアルでは、Javaプログラムで文字列の順列を見つける方法を学びます。これは難しい質問であり、主にJavaのインタビューでよく聞かれます。

Javaにおける文字列の順列のアルゴリズム

最初に文字列から最初の文字を取り出し、残りの文字と順列を作成します。もし文字列が「ABC」であれば、最初の文字はAであり、残りの文字の順列はBCとCBです。次に、最初の文字を順列の利用可能な位置に挿入することができます。BC -> ABC、BAC、BCA CB -> ACB、CAB、CBA 順列を返すための再帰的な関数を作成し、最初の文字を挿入して完全な順列のリストを得るための別の関数を作成できます。

文字列の順列を表示するためのJavaプログラム

package com.scdev.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リポジトリから、例のプログラムのコードをダウンロードすることができます。