一、字符串的排列

题干：

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

成都创新互联是一家专注于成都做网站、网站建设与策划设计,塔什库尔干塔吉克网站建设哪家好?成都创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:塔什库尔干塔吉克等地区。塔什库尔干塔吉克做网站价格咨询:028-86922220

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

示例:

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

限制：

1 <= s 的长度 <= 8

题解：

全排列问题可采用递归的思路，固定某个位置，求出其他位置的全排列

我们可以通过交换来获得所有可能的情况。比如第一个位置上的字符，假如 A 和 A 交换，就相当于第一个位置上固定了 A；假如 A 和 B 交换，B来到第一个位置，就相当于第一个位置上固定了 B；假如 A 和 C 交换，C来到第一个位置，就相当于第一个位置上固定了 C。递归的过程中都是同理。

此外，因为可能有字符重复，我们得到的全排列自然也会有重复，那么我们可以用 set （集合）来去重，并且还可以达到按照字母顺序排序的目的。

代码

class Solution {
public:
set<string> num;

void num_swap(string s,int cnt)
    {
if(cnt==s.size()-1)
        {
            num.insert(s);
return;
        }
for(int i=cnt;i)
        {
// for循环和swap的含义：对于“ABC”，
// 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
// 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
// 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
            swap(s[cnt],s[i]);
            num_swap(s,cnt+1);
            swap(s[cnt],s[i]);
// 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
// 然后进行第三次交换，才能得到"CBA"
        }
    }

    vector<string> permutation(string s) {
        num_swap(s,0);
        vector<string> ans=vector<string>({num.begin(), num.end()});
return ans;
    }
};

本文名称：9.20Leetcode记录
本文路径：http://mswzjz.cn/article/dsoiigh.html