整数字符串的排列

Question

这周我正在做一个 Java 作业，我们期望使用一个集合来递归地回溯一个字符串，并找到所述字符串的所有排列，最终得到一个最大大小的 int字符串中包含的数字。仅此部分就可以了。问题是我们需要设置这个整数的长度，在这里以 int z 显示。

例如，方法 maxDigit("12345",3) 的预期输出为：543。您能否指出我需要改进我的代码的地方？

干杯。

    /**
 * Returns the maximum possible integer given the string str containing digits, using
 * maximum of n digits. Each digit in str can only be used once.
 **/
static int maxDigit(String str, int z) {
    Set<Integer> result = new TreeSet<>();

    if(str.length() == 0 || z == 0)
        return -1;

    permute("",str,result,z);

    int answer = 0;
    for(int a : result) {
        if(a > answer)
            answer = a;
    }
    return answer;
}

/**
 * Creates a set of permutations in result based on string str with max n digits.
 **/
private static void permute(String acc, String str,Set<Integer> result,int z) {
    int n = str.length();
    if (n == 0)
        result.add(Integer.parseInt(acc));
    else {
        if(!(z < str.length())) {
            for (int i = 0; i < n; i++)
                permute(acc + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), result, z);
        } else {
            for (int i = 0; i < n - 1; i++)
                permute(acc + str.charAt(i), str.substring(0, i) + str.substring(i + 1, z), result, z);
        }
    }
}

Answer 1

这似乎有效。你的边缘条件是问题所在。

private static void permute(String acc, String str,Set<Integer> result,int z) {
    int n = str.length();
    if (acc.length() == z)
        result.add(Integer.parseInt(acc));
    else {
        for (int i = 0; i < n; i++)
            permute(acc + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), result, z);

    }
}

System.out.println(maxDigit("1234", 2)); 
43

整数字符串的排列

Permutation of a String of ints

java

recursion

backtracking