剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列

AC-Code

class Solution {private: bool nextPermutation(string& s) { // 首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。 int i = s.size() - 2; while (i >= 0 && s[i] >= s[i + 1]) { i--; } if(i < 0) return false; // 如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i] < a[j]。这样「较大数」即为 a[j]。 int j = s.size() - 1; while (j >= 0 && s[i] >= s[j]) { j--; } swap(s[i], s[j]); // 交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。 reverse(s.begin() + i + 1, s.end()); return true; }private: vector ans; vector vis; void dfs(const string& src, int index, string&& temp) { if(index == src.size()) { ans.push_back(temp); return; } for(int i = 0; i < src.size(); ++i) { if (vis[i] || (i > 0 && !vis[i - 1] && src[i - 1] == src[i])) { continue; } temp.push_back(src[i]); vis[i] = true; dfs(src, index + 1, move(temp)); temp.pop_back(); vis[i] = false; } }public: vector permutation2(string s) { vector ret; sort(s.begin(), s.end()); do { ret.push_back(s); } while (nextPermutation(s)); return ret; } vector permutation(string s) { sort(s.begin(), s.end()); vis.resize(s.size()); dfs(s, 0, move("")); return ans; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。