剑指Offer - 面试题38. 字符串的排列（全排列，排序，回溯+剪枝）

1. 题目

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

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

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

限制：
1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

相关题目：

LeetCode 46. 全排列（回溯）
LeetCode 47. 全排列 II（回溯+搜索剪枝）

2. 解题

class Solution {
	int n;
	vector<string> ans;
	string str;
public:
    vector<string> permutation(string s) {
        sort(s.begin(), s.end());//先排序，后面好剪枝，跳过重复的
        n = s.size(); 
    	vector<bool> visited(n,false);//访问过某字符了
        bt(s,0,visited);
        return ans;
    }

    void bt(string& s, int count, vector<bool>& visited)
    {
    	if(count == n)
    	{
    		ans.push_back(str);
    		return;
    	}
    	for(int i = 0; i < n; ++i)
    	{
    		if(!visited[i])
    		{
    			if(i != 0 && s[i-1] == s[i] && visited[i-1])
    			//if(i != 0 && s[i-1] == s[i] && !visited[i-1])
    				continue;//前一个字符等于当前，跳过
    				//有无!差别是剪枝顺序差别
    				//推荐第二种写法，剪枝更彻底
    			visited[i] = true;
    			str.push_back(s[i]);
    			bt(s,count+1,visited);
    			str.pop_back();
    			visited[i] = false;
    		}
    	}
    }
};

参考解题

最后

以上就是机智荔枝为你收集整理的剑指Offer - 面试题38. 字符串的排列（全排列，排序，回溯+剪枝）的全部内容，希望文章能够帮你解决剑指Offer - 面试题38. 字符串的排列（全排列，排序，回溯+剪枝）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。