时间戳

首页 > 解决方案 > 使用递归查找所有可能的长度为 k 的字符串

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

问题描述

对于字符串 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

标签： javastringalgorithmrecursionsubstring

解决方案

使用回溯逻辑的解决方案（可以泛化以解决任何排列/子集/组合问题） -

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]

推荐阅读