创建字符串的所有元音组合并将每个组合添加到ArrayList可以通过回溯算法来实现。下面是一个示例的Java代码:
import java.util.ArrayList;
import java.util.List;
public class VowelCombinations {
public static void main(String[] args) {
String str = "aeiou";
List<String> combinations = generateVowelCombinations(str);
System.out.println(combinations);
}
public static List<String> generateVowelCombinations(String str) {
List<String> combinations = new ArrayList<>();
backtrack(combinations, str, new StringBuilder(), 0);
return combinations;
}
private static void backtrack(List<String> combinations, String str, StringBuilder sb, int index) {
if (index == str.length()) {
combinations.add(sb.toString());
return;
}
char c = str.charAt(index);
if (isVowel(c)) {
sb.append(c);
backtrack(combinations, str, sb, index + 1);
sb.deleteCharAt(sb.length() - 1);
}
backtrack(combinations, str, sb, index + 1);
}
private static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}
这段代码中,我们首先定义了一个generateVowelCombinations
方法来生成所有元音组合。在该方法中,我们创建了一个空的ArrayList用于存储组合结果,并调用backtrack
方法进行回溯。
backtrack
方法是核心的回溯函数。它接收当前的组合结果sb
、原始字符串str
、当前处理的索引index
作为参数。如果当前索引等于字符串长度,说明已经生成了一个完整的组合,将其添加到结果列表中。
在每一步回溯中,我们检查当前字符是否为元音。如果是元音,将其添加到组合结果sb
中,并递归调用backtrack
方法处理下一个索引。完成递归后,需要将添加的元音字符从组合结果中删除,以便进行下一次回溯。
最后,我们在main
方法中调用generateVowelCombinations
方法,并打印结果列表。
这个算法的时间复杂度是O(2^n),其中n是字符串的长度。每个字符都有两种选择:选择加入组合或不选择加入组合。因此,总共有2^n种组合。
领取专属 10元无门槛券
手把手带您无忧上云