程序员面试金典-面试题 08.07. 无重复字符串的排列组合

题目:

无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。

示例1:

输入:S = "qwe"
输出:["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:

输入:S = "ab"
输出:["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

分析:

遍历字符串中每一个字符,将其插入到已生成的字符串,例如qwe,先生成q,然后遍历到w时,插入到q中,得到qw和wq,再遍历到e时,插入到qw和wq中得eqw,qew,qwe和ewq,weq,wqe。

程序:

class Solution {
    public String[] permutation(String S) {
        Queue<String> queue = new LinkedList<>();
        for(char ch:S.toCharArray()){
            if(queue.isEmpty()){
                queue.offer(String.valueOf(ch));
            }else{
                int len = queue.size();
                for(int i = 0; i < len; ++i){
                    StringBuilder str = new StringBuilder(queue.poll());
                    for(int j = 0; j <= str.length(); ++j){
                        StringBuilder strNew = new StringBuilder(str);
                        strNew.insert(j, ch);
                        queue.offer(strNew.toString());
                    }
                }
            }
        }
        return queue.toArray(new String[0]);
    }
}

 

上一篇:next主题上传github.io界面样式无效


下一篇:docker 安装redis,并且启动,以及常用命令