打印字符串所有排列组合_n个字符构成的字符串,假设每个字符

打印字符串所有排列组合_n个字符构成的字符串,假设每个字符1)子序列是不要求连续的各个位置的字符拼接而成的字符串,子串是连续位置拼接成的字符串2)暴力递归,就是大问题,完全可以拆成规模更小,但是解决同类型的问题

打印字符串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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注