LeetCode刷题【剑指 Offer 38】字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

 

限制：

1 <= s 的长度 <= 8

\n

题解

看起来有点面熟，很直白的深度搜索回溯算法。

根据所给字符串s，挨个位置遍历，在新得出的字符串的每一位上穷举，并记录已举过的字符串，在穷举的时候，如果已经存在于已使用过的位置的集合的记录中，则跳过。

而最终要求“里面不能有重复元素”，所以最终的结果集用set集合保存，直接进行去重。

class Solution {


    private HashSet<String> list;

    private Integer length;

    public String[] permutation(String s) {
        list = new HashSet<>();
        length = s.length();
        HashSet<Integer> visited = new HashSet<>();
        dfs(s.toCharArray(),visited,0,new char[s.length()]);
        return list.toArray(new String[0]);
    }


    private void dfs(char[] charArr,HashSet<Integer> visited,int index,char[] newCharArr){
        if (index==length){
            list.add(new String(newCharArr));
            return;
        }
        for (int i = 0; i < charArr.length; i++) {
            if (visited.contains(i)){
                continue;
            }
            visited.add(i);
            newCharArr[index] = charArr[i];
            dfs(charArr,visited,index+1,newCharArr);
            visited.remove(i);
        }
    }
}

结果

解答成功:
执行耗时:69 ms,击败了10.93% 的Java用户
内存消耗:44.2 MB,击败了21.26% 的Java用户

而在结果集没有使用set集合的时候，跑这样一个用例出了问题。

测试用例:"aab"
测试结果:["aab","aba","aab","aba","baa","baa"]
期望结果:["aba","aab","baa"]

所以，取第一个a还是第二个a是没有区别的，这边之前记录的是HashSet<Integer> visited字符串的索引位置，所以在此之外，可以再借助一个字符串集合进行剪枝操作Set<Character> sameChar。剪枝之后的结果集也可以不用set集合了，直接更简单的List集合替代。

另外还有一点小小的改动，一开始写的visited是Set集合，而记录内容是某个索引位置是否访问过，都知道索引的特征是从0-N连续的，这边可以再简化成一个boolean[] visited数组。

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


    private List<String> list;

    private Integer length;

    public String[] permutation(String s) {
        list = new ArrayList<>();
        length = s.length();
        boolean[] visited = new boolean[s.length()];
        dfs(s.toCharArray(),visited,0,new char[s.length()]);
        String[] res = new String[list.size()];
        int i = 0;
        for (String s1 : list) {
            res[i] = s1;
            i++;
        }
        return res;
    }


    private void dfs(char[] charArr,boolean[] visited,int index,char[] newCharArr){
        if (index==length){
            list.add(new String(newCharArr));
            return;
        }
        Set<Character> sameChar = new HashSet<>();
        for (int i = 0; i < charArr.length; i++) {
            if (visited[i]){
                continue;
            }
            if (sameChar.contains(charArr[i])){
                continue;
            }
            sameChar.add(charArr[i]);
            visited[i] = true;
            newCharArr[index] = charArr[i];
            dfs(charArr,visited,index+1,newCharArr);
            visited[i] = false;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

解答成功:
执行耗时:14 ms,击败了64.61% 的Java用户
内存消耗:42.7 MB,击败了73.19% 的Java用户