(搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了(搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❓剑指 Offer 38. 字符串的排列

难度：中等

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

💡思路：回溯

可以直接暴力穷举，但是如果字符串 s 内有重复字符，要考虑怎么去重。

先对原始的字符串进行排序，保证相同的字符都相邻；
然后定义一个 hasUsed 数组来保存每一位是否被访问过;
在递归函数中，我们限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」，即
- 当 i > 0 && s[i - 1] == s[i] && !hasUsed[i - 1] 时，则 continue 跳过，即可去重。
- 这个限制条件保证了对于重复的字符，我们一定是从左往右依次加入字符串中的。

🍁代码：(C++、Java)

C++

class Solution {
private:
    vector<string> ans;

    void backtracking(const string& s, string& temp, vector<int>& hasUsed){
        if(temp.size() == s.size()){
            ans.push_back(temp);
            return;
        }
        for(int i = 0; i < s.size(); i++){
            if(hasUsed[i] == 1) continue;
            //去重
            if(i > 0 && s[i] == s[i - 1] && hasUsed[i - 1] == 0) continue;

            hasUsed[i] = 1;
            temp.push_back(s[i]);
            backtracking(s, temp, hasUsed);
            temp.pop_back();
            hasUsed[i] = 0;
        }
    }
public:
    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        string temp;
        vector<int> hasUsed(s.size(), 0);
        backtracking(s, temp, hasUsed);
        return ans;
    }
};

Java

class Solution {
    private ArrayList<String> ret = new ArrayList<>();

    private void backtracking(char[] cs, StringBuffer temp, int[] hasUsed){
        if(temp.length() == cs.length){
            ret.add(temp.toString());
            return;
        }
        for(int i = 0; i < cs.length; i++){
            if(hasUsed[i] == 1) continue;
            //去重
            if(i > 0 && cs[i] == cs[i - 1] && hasUsed[i - 1] == 0) continue;

            hasUsed[i] = 1;
            temp.append(cs[i]);
            backtracking(cs, temp, hasUsed);
            temp.deleteCharAt(temp.length() - 1);
            hasUsed[i] = 0;
        }
    }
    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        StringBuffer temp = new StringBuffer();
        int[] hasUsed = new int[cs.length];
        backtracking(cs, temp, hasUsed);
        //转换为 String[] 型
        int n = ret.size();
        String[] ans = new String[n];
        for(int i = 0; i < n; i++){
            ans[i] = ret.get(i);
        }
        return ans;
    }
}