字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

代码

class Solution {
    string str;
    vector<string> ans;
    unordered_map<int, int> mp;
    unordered_map<char, int> hash;
public:
    void hashCalc() {
        for (int i = 0, k = 1; i < str.size(); ++i) {
            if (hash.find(str[i]) == hash.end()) {
                hash[str[i]] = k++;
            }
        }
    }

    vector<string> Permutation(string str) {
        if (str.size() > 0) {
            this->str = str;
            hashCalc();
            dfs(0, 0);
        }
        return ans;
    }
    
    void dfs(int p, int tag) {
        if (mp.find(tag) != mp.end()) {
            return;
        }
        mp[tag] = 1;
        if (p >= str.size()) {
            ans.push_back(str);
        }
     	//因为swap只交换一次，str会改变，所以需要记住交换前的,从而不影响下一轮操作，关键
        string tmp = str;
        for (int i = p; i < str.size(); ++i) {
            swap(str[p], str[i]);//只交换一次，后面不再交换回来，保证每次交换str[p+1,n]子串都是从最小的先开始
            dfs(p + 1,  10 * tag + hash[str[p]]);
        }
        str = tmp;
    }
};