[剑指offer] 27. 字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
题目就是考察排列的算法，利用递归+回溯解决
注意去重
class Solution { public: vector<string> res; vector<string> Permutation(string str) { if(str=="") return res; helper(str, 0, str.length() - 1); sort(res.begin(),res.end()); return res; } void helper(string &str, int beg, int end) { set<char> hasSwap; if (beg >= end) res.push_back(str); else for (int i = beg; i <= end; i++) { if (hasSwap.find(str[i]) == hasSwap.end()) { hasSwap.insert(str[i]); swap(str[i], str[beg]); helper(str, beg + 1, end); swap(str[i], str[beg]); } } } };