剑指 Offer 38. 字符串的排列

题目

剑指 Offer 38. 字符串的排列

我的思路

如果原字符串的各个字符不相同，那么结果列表中字符串的个数是n！个，所以不论如何解决本题目，时间复杂度一定是n!。

如果存在相同字符，那么搜索时需要“剪枝”。如何合理地剪枝？我原本的想法是用一颗字典树，空间复杂度会达到n！。但其实，在深搜时，递归调用已经隐含了树地层次结构，只需要在每个调用层中存储当前分支已搜索的子树节点即可，回溯并搜索另一个节点时此前的存储空间被释放。把空间复杂度降到了n*n。

我的实现

class Solution {
public:
    vector<string> result;
    void dps(string rStr,string nStr){
        if(rStr.size()==0){
            result.push_back(nStr);
            return;
        }
        unordered_set<char> visited;
        for(int i=0;i<rStr.size();i++){
            if(!visited.count(rStr[i])){
                visited.insert(rStr[i]);
                string temp(rStr);
                temp.erase(temp.begin()+i);
                dps(temp,nStr+rStr[i]);
            }
        } 
        visited.clear();
    }
    vector<string> permutation(string s) {
        string init = "";
        dps(s,init);
        return result;


    }
};
/*
可以以阶乘的复杂度遍历所有字符串排列，然后去重。
去重的方法：用一个树形结构存储所有已经遍历的字符串排列
时间复杂度n!;
空间复杂度n!.

可优化，如果使用深搜递归遍历，那么递归调用的过程其实是树向下探的过程，那么隐含的有一个树的结构。只需要在每一层调用设置一个辅助变量记录当前层已经遍历的字符，那么当前层就可以保证不遍历到重复的字符。而递归返回到高层时，同时会释放已访问过子树的结构，所以不需要随时记录一颗完整的树，降低了空间复杂度。
 
*/

拓展学习

我的解决方案中时通过选择剩余字符串中的某个字符，把它截取掉，从而得到新的剩余字符串。截取的过程其实会发生一段子串复制，式复杂度增加。官方题解中通过依次把剩余串中的首字符与其余字符交换的方式，只用只用交换两个字符元素就完成了选择当前位置字符的工作。

class Solution {
public:
    vector<string> result;
    vector<string> permutation(string s) {
        dfs(s, 0);
        return result;
    }
    void dfs(string& s, int pos) {
        if (pos >= s.size()) {
            result.push_back(s);
            return;
        }
        for (int i = pos; i < s.size(); ++i) {
            if (judge(s, pos, i)) continue;   // 如果pos和i之间有字符等于s[i]，则跳过。
            swap(s[pos], s[i]);
            dfs(s, pos+1);
            swap(s[pos], s[i]);
        }
    }

    bool judge(string& s, int start, int end) {
        for (int i = start; i < end; ++i) {
            if (s[i] == s[end]) return true;
        }
        return false;
    }
};