java - 用递归找到所有可能的长度为 k 的字符串

Question

对于字符串 s = "abcd",k=3 那么答案应该是:

abc
abd
acd
bcd

带有递归(k=3)的java代码:

public class SubString {

    static ArrayList<String> al = new ArrayList<>();

    public static void main(String[] args) {
        String s = "abcd";
        findsubsequences(s, ""); // Calling a function
        for (String subString : al) {
            if (subString.length() == 3) {
                System.out.println(subString);
            }
        }
    }

    public static void findsubsequences(String s, String ans) {
        if (s.length() == 0) {
            al.add(ans);
            return;
        }
        findsubsequences(s.substring(1), ans + s.charAt(0));
        findsubsequences(s.substring(1), ans);
    }
}

我想通过递归以最快的方式找到所有可能的长度为 k 的子串，并且在 arraylist 中不使用 foreach

Answer 1

使用回溯逻辑的解决方案(可以推广以解决任何排列/子集/组合问题)-

public static void main(String[] args) {
    ans = new ArrayList<>();
    String s = "abcd";
    int k = 3;
    generatePermutation(new StringBuilder(""), 0, s.toCharArray(), k);
    System.out.println(ans);
}

private static List<String> ans;

private static void generatePermutation(StringBuilder temp, int st, char[] str, int k){
    if(temp.length() == k){
        // base result
        String br = temp.toString();
        ans.add(br);
        return;
    }
    
    for(int i = st; i < str.length; i++){
        temp.append(str[i]);
        generatePermutation(temp, i + 1, str, k);
        temp.setLength(temp.length() - 1);
    }
}

输出 :

[abc, abd, acd, bcd]