38. 字符串的排列
1. 描述
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
2. 例子
示例 1:
输入：s = “abc”
输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
3. 限制
- 1 <= s 的长度 <= 8
4. 题解
时空复杂度有些复杂，不会分析
class Solution
{
bool nextPermutation(string &m_letters)
{
int lastReversedIndex = 0;
for(int i = m_letters.size() - 1; i >= 0; i--)
{
if(i == 0) return false;
if(m_letters[i] > m_letters[i - 1])
{
lastReversedIndex = i;
break;
}
}
int leastBiggerIndex = lastReversedIndex;
for(int i = leastBiggerIndex; i < m_letters.size(); i++)
{
if(m_letters[i] > m_letters[lastReversedIndex - 1] && m_letters[i] < m_letters[leastBiggerIndex])
leastBiggerIndex = i;
}
swap(m_letters[leastBiggerIndex], m_letters[lastReversedIndex - 1]);
sort(m_letters.begin() + lastReversedIndex, m_letters.end());
return true;
}
public:
// vector<string> permutation(string s)
vector<string> permutation(string &m_letters)
{
sort(m_letters.begin(), m_letters.end());
vector<string> permutations{m_letters};
while(nextPermutation(m_letters))
permutations.push_back(m_letters);
return permutations;
}
};