【剑指Offer】38. 字符串的排列

绝地灬酷狼 2022-11-29 05:37 106阅读 0赞

[NowCoder][]

## 题目描述 ##

输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。注意字典顺序

import java.util.*;
    import java.lang.*;
    public class Solution { 
        private Set<String> set = new HashSet<>(); // 去重
        private ArrayList<String> ret = new ArrayList<>(); // 返回
        
        public ArrayList<String> Permutation(String str) { 
            if(str.length() == 0) return ret;
            boolean[] visited = new boolean[str.length()];
            
            dfs(str, "", visited);
            
            // 有序
            // （1.循环Set->ArrayList）
            String[] sarr = set.toArray(new String[set.size()]);
            Arrays.sort(sarr);
            for(String s : sarr) { 
                ret.add(s);
            }
            
            return ret;
        }
        // 回溯递归-全排列
        private void dfs(String s, String ch, boolean[] visited) { 
            // 一组排列
            if(s.length() == ch.length()) { 
                set.add(ch);
                return;
            }
            
            for(int i = 0; i < s.length(); i++) { 
                char temp = s.charAt(i);
                if(visited[i]) continue;
                visited[i] = true;
                dfs(s, ch + String.valueOf(temp), visited);
                visited[i] = false;
            }
        }
    }

Stream函数编程[https://bennyrhys.blog.csdn.net/article/details/108097008][https_bennyrhys.blog.csdn.net_article_details_108097008]  
可以排序可以防止重复

ret = set.stream()
                .sorted()
                .collect(Collectors.toCollection(ArrayList::new));
            
            return ret;

[NowCoder]: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[https_bennyrhys.blog.csdn.net_article_details_108097008]: https://bennyrhys.blog.csdn.net/article/details/108097008