时间戳

首页 > 解决方案 > 查找单词中不重复字母的所有排列

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

问题描述

给定 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);
}

标签： javaalgorithmrecursion

解决方案

我使用的算法非常简单。使每个字符成为字符串的第一个字符，并找到与其他两个字符的组合。所以对于字符 c、a、t 的组合将是

c at
c ta

a ct
a tc

t ca
t ac

代码：

static void findWords(String str, int pos) {
    if(str == null || pos < -1) {
        return;
    }

    int len = str.length();
    if(pos + 1 < len) {
        findWords(str, pos + 1);
    }

    //find char swap positions
    int pos1 = (pos + 1) % len;
    int pos2 = (pos - 1 + len) % len;

    char[] chars = str.toCharArray();
    String str1 = new String(new char[] {chars[pos], chars[pos1], chars[pos2]});
    String str2 = new String(new char[] {chars[pos], chars[pos2], chars[pos1]});

    System.out.println(str1);
    System.out.println(str2);
}

public static void main(String[] args) {
    String word = new String("abc");
    findWords(word, 0);
}

推荐阅读