java - 递归方法，接受输入 s 和 k 并生成长度为 k 的所有字符串

Question

我需要编写一个递归方法，它接受输入 s 和 k 并生成所有长度为 k 的字符串，这些字符串满足没有两个连续位置包含相同符号的属性。整数1、2、3、4、5、6、7代表符号。

例如，当 s = 4 且 k = 3 且选择的字母表为 {1, 2, 3, 4} 时，字符串数量为 36，字符串为:121、123、124、131、132、134、141、142、143、212、213、214、231、232、234、241、242、243、312、313、314、321、323、324、3 41、342、343、412、413、414、421、423、424、431、432、434。

我不需要打印所有字符串，我只需生成它们即可计算总数并将其放入表格中。

到目前为止我的代码:

public static int generateNum(int k, int s){

    if (k==1){
        return s;
    }
    if (s==1 && k>1){
        return 0;
    }
}

我仍在学习递归，我不知道如何解决这个问题!任何帮助都会很棒。

Answer 1

如果您只需要总数:

对于任意 k > 0 且 s > 0，可以直接返回答案 s*Math.pow(s-1,k-1);否则返回0。

如果需要获取字符串:

假设我们将生成的字符串保存到 ArrayList 中，代码如下:

public static int generateNum(int k, int s) {
    List<String> resultList = new ArrayList<>();
    processRecursion(resultList, "", s, k);
    return resultList.size();
}

private static void processRecursion(List<String> list, String finishedStr, int s, int unfinishedCount) {
    if (unfinishedCount == 0 && !finishedStr.isEmpty()) {
        list.add(finishedStr);
        return;
    }

    for (int i = 1; i <= s; i++) {
        if (!finishedStr.isEmpty() && finishedStr.codePointAt(finishedStr.length()-1) == 0x30 + i) {
            continue;
        }
        processRecursion(list, finishedStr + i, s, unfinishedCount - 1);
    }
}