Leetcode题解剑指 Offer 38. 字符串的排列

PROBLEM

难度中等

MY ANSWER

使用回溯，vis标记访问过的字符，使用set记录得到的结果，若重复则不保存到最终结果中。时间空间复杂度都很高，因为没有剪枝。

class Solution {
public:
    vector<string> res;
    string s;
    vector<int> vis;
    set<string> ans;
    void select(string str) {
        if(str.length() == s.length()) {
            if(ans.insert(str).second) {
                res.push_back(str);
            }         
            return;
        }
        else {
            for(int i = 0; i < vis.size(); i++) {
                if(!vis[i]) {
                    vis[i] =  1;
                    select(str + s[i]);
                    vis[i] = 0;
                }
            }
        }
    }
    vector<string> permutation(string s) {
        this->s = s;
        vis.resize(s.length());
        select("");
        return res;
    }
};

BETTER SOLUTION

回溯剪枝

首先将字符串排序，当有重复的字符，只选择第一个进行回溯，就避免了重复的字符串。时间复杂度O(n*n!)，空间复杂度O(n)。

class Solution {
public:
    vector<string> res;
    string s;
    vector<int> vis;
    void select(string str) {
        if(str.length() == s.length()) {
            res.push_back(str);      
            return;
        }
        else {
            for(int i = 0; i < vis.size(); i++) {
                if(vis[i] || (i > 0 && !vis[i-1] && s[i-1] == s[i])) {
                    continue;
                }
                vis[i] = 1;
                select(str + s[i]);
                vis[i] = 0;
            }
        }
    }
    vector<string> permutation(string s) {
        vis.resize(s.length());
        sort(s.begin(), s.end());
        this->s = s;
        select("");
        return res;
    }
};

下一个排列

首先将字符串排序，然后通过交换来生成下一个字典序的排列。具体做法就是从尾部开始朝前遍历，记录第一个降序的字符，将其与前面遍历过的第一个比它大的字符交换，再将后面的字符串反转，就得到了下一个字典序的字符串。时间复杂度O(n*n!)，空间复杂度O(1)。

例子：1238640 -> 1248630 -> 1240368。

class Solution {
public:
    bool nextPermutation(string& s) {
        int i = s.size() - 2;
        while (i >= 0 && s[i] >= s[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = s.size() - 1;
        while (j >= 0 && s[i] >= s[j]) {
            j--;
        }
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());
        return true;
    }

    vector<string> permutation(string s) {
        vector<string> ret;
        sort(s.begin(), s.end());
        do {
            ret.push_back(s);
        } while (nextPermutation(s));
        return ret;
    }
};

SUMMARY

回溯算法模板backtrack

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

sort(begin迭代器, end迭代器)，可排列字符串，直接在字符串上进行从小到大排列，即改变了原来的字符串。
全排列去重可以先对其进行排序，对重复选择的分支进行剪枝就可以去重。
reverse(begin迭代器, end迭代器)，迭代器直接通过加法来访问后面的迭代器。