?劍指 Offer 38. 字符串的排列

難度：中等

輸入一個(gè)字符串，打印出該字符串中字符的所有排列。

你可以以任意順序返回這個(gè)字符串?dāng)?shù)組，但里面 不能有重復(fù)元素。

示例:

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

限制：

• 1 <= s 的長(zhǎng)度 <= 8

??思路：回溯

可以直接暴力窮舉，但是如果字符串 s 內(nèi)有重復(fù)字符，要考慮怎么去重。

• 先對(duì)原始的字符串進(jìn)行排序，保證相同的字符都相鄰；
• 然后定義一個(gè) hasUsed 數(shù)組來(lái)保存每一位是否被訪問(wèn)過(guò);
• 在遞歸函數(shù)中，我們限制每次填入的字符一定是這個(gè)字符所在重復(fù)字符集合中「從左往右第一個(gè)未被填入的字符」，即
  • 當(dāng) i > 0 && s[i - 1] == s[i] && !hasUsed[i - 1] 時(shí)，則 continue 跳過(guò)，即可去重。
  • 這個(gè)限制條件保證了對(duì)于重復(fù)的字符，我們一定是從左往右依次加入字符串中的。

??代碼：(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);
        //轉(zhuǎn)換為 String[] 型
        int n = ret.size();
        String[] ans = new String[n];
        for(int i = 0; i < n; i++){
            ans[i] = ret.get(i);
        }
        return ans;
    }
}

?? 運(yùn)行結(jié)果：

?? 復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n?n!)$，其中 n 為給定字符串的長(zhǎng)度。這些字符的全部排列有 $O(n!)$ 個(gè)，每個(gè)排列平均需要 $O(n)$的時(shí)間來(lái)生成。
• 空間復(fù)雜度：$O(n)$，我們需要 $O(n)$ 的?？臻g進(jìn)行回溯，注意返回值不計(jì)入空間復(fù)雜度。。

題目來(lái)源：力扣。

放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁(yè) / CSDN—力扣專欄，每日更新！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-659842.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(搜索) 劍指 Offer 38. 字符串的排列 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！