生成范围内所有可能的字符串

Question

我需要生成特定范围内所有可能的字符串。例如
上限 - aaa
低界 - ccc

还有可能的情况 aab-caa , hhu - kkk , 但不是 aaz - ccc 值应为

    aaa
    aab
    aac
    aba
    abb
    abc
    aca
    acb
    acc
    caa
    cab
    cac
    cca
    ccb
    ccc

我写了这样的方法，但它不能正常工作，我不知道如何正确地做到这一点，我现在很难捕捉到所有可能的情况，请帮助

 public static List<String> generateAllPossibleStrings(String start, String end) {
        if (start.length() != end.length()) {
            return null;
        }
        List<String> variants = new ArrayList<>();
        char startArray[] = start.toCharArray();
        char endArray[] = end.toCharArray();
        char currentArray[] = Arrays.copyOf(startArray, startArray.length);
        variants.add(new String(currentArray));
        for (int i = startArray.length - 1; i >= 0; i--) {
            while (currentArray[i] != endArray[i]) {
                currentArray[i]++;
                variants.add(new String(currentArray));
                for (int j = startArray.length - 1; j > i; j--) {
                    while (currentArray[j] != endArray[j]) {
                        currentArray[j]++;
                        variants.add(new String(currentArray));
                    }
                    currentArray[j] = startArray[j];

                }
            }
            currentArray[i] = startArray[i];
        }

        System.out.println(Arrays.toString(variants.toArray()));
        return variants;
    }

对于上面的例子，我得到了

[aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bca, caa, cab, cac, cba, cca]

如您所见，缺少一些值。

请帮助更正此方法并使其正常工作，或者它应该作为递归方法实现。

解释

为什么 aaz - ccc 不可能，因为在此示例中，下限 (ccc) 中的任何字符都应大于上限 (aaz) 中的相应字符 z 大于 c 所以这是不正确的。

Answer 1

编辑：我可能误解了这个问题，我认为结束字符串在每个位置都在开始字符串之上，但从您的其他示例来看情况似乎并非如此。你能展示你应该在 hhu-kkk 上输出什么，并解释 aaz-ccc 有什么问题吗？

EDIT2 : 正如我所怀疑的，hhu-kkk 也是一个错误的输入 (u>k)，您应该再次编辑您的问题。

将字符串视为您递增的数字。

当您在一个位置超过结束字符串时，您将代替开始字符串的字母并递增下一个字母，就像带进位的加法一样。

这是您的代码的修改版本。它现在还会检查这两个字符串是否满足您描述的所有属性（如果函数使用正确，这不是必需的）。

public static List<String> generateAllPossibleStrings(String start, String end) {
    if(start==null||end==null)
        return null;
    if (start.length() != end.length())
        return null;
    int n = start.length();
    List<String> variants = new ArrayList<>();
    char startArray[] = start.toCharArray();
    char endArray[] = end.toCharArray();
    char currentArray[] = Arrays.copyOf(startArray, startArray.length);
    variants.add(new String(currentArray));

    //We check if the start string is really above the end string as specified
    //We output an empty string if it is not the case
    boolean possible = true;
    for(int i = 0; i<n; i++)
        possible = possible && (startArray[i]<=endArray[i]);
    if (!possible)
        return variants;


    while(!end.equals(new String(currentArray))){
        currentArray[n-1]+=1;
        int i = n-1;
        while(currentArray[i]>endArray[i]){
            currentArray[i]=startArray[i];
            i--;
            currentArray[i]++;
        }
        variants.add(new String(currentArray));
    }

    System.out.println(Arrays.toString(variants.toArray()));
    return variants;
}

Answer 2

我会使用 single responsibility principle，将实现拆分为清晰的小方法并使用递归

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

public final class Permutations {

    public static List<String> generate(String begin, String end) {
        List<String> result = new ArrayList<>();

        String current = begin;
        while (true) {
            result.add(current);
            if (current.equals(end))
                break;
            current = getNextPermutation(current, end);
        }

        return result;
    }

    private static String getNextPermutation(String current, String end) {
        char[] candidate = current.toCharArray();
        createNextPermutation(candidate, current.length()-1, end);
        return String.valueOf(candidate);
    }

    private static void createNextPermutation(char[] candidate, int index, String end) {
        char c = getNextChar(candidate[index]);
        if (c > end.charAt(index)) {
            candidate[index] = 'a';
            createNextPermutation(candidate, index-1, end);
        }
        else {
            candidate[index] = c;
        }
    }

    private static char getNextChar(char c) {
        return (char)(c + 1);
    }
}

生成范围内所有可能的字符串

Generate all possible strings in a range

java

algorithm

recursion

loops

brute-force