打印字符串s的所有子序列,打印字面不重复的子序列
提示:区分子序列和子串
题目
打印字符串s的所有子序列
也打印字面不重复的子序列
(1)所谓子序列:是s各个位子的字符,要还是不要,组成的任意序列串
比如;s=abcde
ad,ae,acd,等等,随意可不连续的子序列
(2)所谓子串:必须是s中连续的任意子串
s=abcde
子串是:a,ab,abc,bcd等等,必须是连续的
(3)所谓字面不重复:是子序列没有相等的情况
比如
s=aabcde
会出来0位置a和b组合ab
会出来1位置a和b组合ab
这里字面值一样,需要去重
只打印一个ab
打印子序列
那咱们可以从i=0–N-1位置,依次遍历,每次遍历到i位置时,决定是要i还是不要i
每一种情况都收集,沿途拼接子序列为path,最后到N位置,就可以打印了
定义函数f(s, i,path)
代表来到s的i位置,决定要还是不要,把i位置拼到path上
当i=N时,打印这一路拼接的子序列path
对于0–i-1范围上的字符串已经确定拼接到path中了,还有i–N-1范围内的没确定
不管i在哪,f(i)都是一个规模不同的子问题,要解决的事情是同样的
所以就可以暴力递归实现。
手撕代码实现:
//复习打印子序列:
//那咱们可以从i=0--N-1位置,依次遍历,每次遍历到i位置时,决定是要i还是不要i
//每一种情况都收集,沿途拼接子序列为path,最后到N位置,就可以打印了
public static void f(char[] str, int i, String path){
if (i == str.length){
//一条路径决策完成
System.out.print(path +" ");
return;
}
//还没越界
f(str, i +1, path + String.valueOf(str[i]));//要i
f(str, i +1, path);//不要i
//每个递归放的path都不一样,所以不必恢复现场
}
//调用,讲s转化为str
public static void reviewPrint(String s){
if (s == null || s.length() == 0 || s.compareTo("") == 0) return;
char[] str = s.toCharArray();
f(str, 0, "");
}
public static void test(){
String s = "abcd";
ArrayList<String> res = subString(s);
for (String s1:res){
System.out.print(s1 +" ");
}
System.out.println("\n复习:");
reviewPrint(s);
}
打印结果:
abcd abc abd ab acd ac ad a bcd bc bd b cd c d
复习:
abcd abc abd ab acd ac ad a bcd bc bd b cd c d
若想要打印字面不重复的子序列呢?
哈希集合可以自动去重,在产生不同的path之后,完全可以把他们加入哈希集中,就没了重复值了。
//如果一个字符串中有重复的字符,希望输出没有重复的字符串,消除重复
//HashSet就能自动消除--------------包括哈希表,都是可以自动消除重复值的
public static HashSet<String> subStringNoRepeat(String s){
if (s == null || s.length() == 0) return null;//空串
ArrayList<String> res = new ArrayList<>();
char[] str = s.toCharArray();
String path = "";//从空串开始拼接
process(str, 0, res, path);
//从str的0位置开始拼接,正在拼接的子序列为path,拼好的字符串放在res中
//消除重复
HashSet<String> set = new HashSet<>();
for (String s1:res){
set.add(s1);
}
//最后返回res,所有的可能性
return set;
}
//暴力递归找可能的子序列的递归过程
public static void process(char[] str, int i, ArrayList<String> res, String path){
if (i == str.length){
//如果i已经到了末端,说明可能性都考虑完了,得到了一个可能的结果
res.add(path);
return;
}
//正在i位置的,决定是要i处的字符呢,还是不要,两个分支递归迭代
process(str, i + 1, res, path + String.valueOf(str[i]));//要了i的字符,拼接,然后继续处理i+1
process(str, i + 1, res, path);//不要i位的字符拼接
}
public static void test2(){
String s = "aabc";
HashSet<String> res = subStringNoRepeat(s);
for (String s1:res){
System.out.println(s1);
}
System.out.println("\n不去重的话:");
reviewPrint(s);
}
public static void main(String[] args) {
test();
// test2();
}
测试一把:
aa ab a bc aac ac b aab abc c aabc
不去重的话:
aabc aab aac aa **abc** ab ac a **abc** ab ac a bc b c
哈希集可以自动去重
总结
提示:重要经验:
1)子序列是不要求连续的各个位置的字符拼接而成的字符串,子串是连续位置拼接成的字符串
2)暴力递归,就是大问题,完全可以拆成规模更小,但是解决同类型的问题。
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。
今天的文章打印字符串所有排列组合_n个字符构成的字符串,假设每个字符分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/85431.html