java - 字符串的子序列

Question

我必须编写一个程序，它接受字符串参数 s 和整数参数 k，并打印出长度为 k 的 s 的所有子序列。例如，如果我有

subSequence("abcd", 3);

输出应该是

 abc abd acd bcd

我想要指导。没有代码，请!

提前致谢。

更新:

我正在考虑使用这个伪代码:

Start with an empty string
Append the first letter to the string 
  Append the second letter
    Append the third letter 
    Print the so-far build substring - base case
  Return the second letter
    Append the fourth letter
    Print the substring - base case
Return the first letter
   Append the third letter
     Append the fourth letter
     Print the substring - base case
   Return third letter
Append the second letter
   Append the third letter
     Append the fourth letter
     Print the substring - base case
   Return the third letter
Return the second letter
Append the third letter
   Append the fourth letter
Return third letter
Return fourth letter
Return third letter
Return second letter
Return first letter

不同的缩进意味着递归调用更深入。

(回应迭戈·塞维利亚):

按照您的建议:

private String SSet = "";
private String subSequence(String s, int substr_length){
    if(k == 0){
       return SSet;
    }
    else{
    for(int i = 0; i < substr_length; i++){
        subString += s.charAt(i);
        subSequence(s.substring(i+1), k-1);
    }
   }
    return SSet;
}
}

Answer 1

当您将“递归”作为标签时，我将尝试向您解释解决方案的策略。递归函数应该是像您显示的那样的函数:

subSequence(string, substr_length)

实际上返回一个(子)字符串的集合。请注意如何将问题划分为易于递归的子问题。每个 subSequence(string, substr_length) 应该:

1. 从一个空子字符串集开始，我们称之为 SSet。
2. 从 0 到字符串长度减去 substr_length 进行循环
3. 在每个循环位置 i 中，以 string[i] 作为起始字符，并递归调用 subSequence(string[i+1..length], substr_length - 1) (此处 .. 暗示字符串中的索引范围，因此您必须使用这些索引创建子字符串)。对 subSequence 的递归调用将返回大小为 substr_length -1 的所有字符串。您必须在所有这些子字符串前面添加您选择的字符(在本例中为 string[i])，并将它们全部添加到 SSet 集中。
4. 只需返回构造好的SSet。该字符串将包含所有子字符串。

当然，这个过程是高度可优化的(例如使用动态编程存储长度为 i 的所有子字符串)，但您明白了。