Java字符串全排列算法详解：高效实现与应用

3 年 ago
新, 韵
2 minutes

这是文章《如何在Java中找到字符串的所有排列》的第1部分（共1部分）。

在本教程中，我们将学习如何在Java程序中找到字符串的所有排列。这是一个常见且具有挑战性的问题，经常在Java面试中被问到。

在Java中生成字符串排列的算法

我们将首先从字符串中取出第一个字符，然后与剩余字符进行排列。例如，如果字符串为“ABC”，第一个字符是“A”，剩余字符的排列有“BC”和“CB”。现在，我们可以将第一个字符插入到这些排列中的所有可用位置。对于“BC”，插入“A”可以得到“ABC”、“BAC”、“BCA”；对于“CB”，插入“A”可以得到“ACB”、“CAB”、“CBA”。我们可以编写一个递归函数来生成剩余字符的排列，然后再编写另一个辅助函数来将第一个字符插入到这些排列中，从而获得完整的排列列表。

使用Java程序打印字符串的排列

package com.Olivia.java.string;

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

/**
 * Java程序，用于查找字符串的所有排列
 * @author Pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        // 处理错误场景
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // 第一个字符
        String rem = str.substring(1); // 除去第一个字符的剩余字符串
        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("\n字符串 " + s + " 的排列组合是: \n" + permutationFinder(s));
        System.out.println("\n字符串 " + s1 + " 的排列组合是: \n" + permutationFinder(s1));
        System.out.println("\n字符串 " + s2 + " 的排列组合是: \n" + permutationFinder(s2));
    }
}

我使用了Set（具体是HashSet）来存储字符串的排列组合。这样做可以自动去除重复项，确保每个排列都是唯一的。

输出结果

字符串 AAC 的排列组合是: 
[AAC, ACA, CAA]

字符串 ABC 的排列组合是: 
[ACB, ABC, BCA, CBA, CAB, BAC]

字符串 ABCD 的排列组合是: 
[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仓库下载示例程序代码。

bannerAds