java - 查找单词中非重复字母的所有排列

Question

给定 3 个不同的字母:你能否使用递归函数打印字母的六种可能的非重复组合。 'cat' 应输出:cat、act、atc、tac、tca 和 cta。这是我的程序，我找不到递归算法。这是我的尝试:

 static void findWords(StringBuilder string, int start, int stride) {
    //1. iterate through all possible combinations of the chars recursively

    System.out.println(string);

    if (stride < string.length() && start < string.length())
    {
        char temp = string.charAt(stride);
        string.setCharAt(stride, string.charAt(start));
        string.setCharAt(start, temp);

        findWords(string, start, stride + 1);

        findWords(string, start + 1, stride + 1 );


    }
}

public static void main(String[] args)
{

   StringBuilder word = new StringBuilder("cat");
   findWords(word,0,1);
}

Answer 1

解决方法:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static List<String> resultList = new ArrayList<>();

    static void computeResult(char[] s, int pos, String resultString) {
        if (pos == 3) {
            resultList.add(resultString);
            return;
        }
        for (int i = 0; i < 3; ++i) {
            if (!resultString.contains(String.valueOf(s[i]))) {
                computeResult(s, pos + 1, resultString + s[i]);
            }
        }
    }

    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();
        computeResult(s, 0, "");
        for(String str : resultList) {
            System.out.println(str);
        }
    }
}

解释:

递归是由 computeResult 函数完成的。它以一个空字符串开始，然后遍历所有可能的字母“c”、“a”和“t”，将它们附加到 resultString，现在有 3 个字符串，对于每个字符串，函数 computeResult 被再次调用。然后它做同样的事情，并且只将那些尚未添加的字母添加到 resultString，因此我们向 'c' 添加 'a' 导致 'ca' 和 't'，导致 'ct'，我想想剩下的你自己想办法吧。

请注意，如果字母是唯一的，则此方法有效。如果不是，例如给定字符串 'tat'，您可以将其转换为 t1a1t2 并对数组 ['t1', 'a1', 't2'] 执行相同的过程，然后删除数字。