当前位置：首页 > news >正文

【LeetCode】剑指 Offer（20）

news 2025/9/13 0:12:45

题目：剑指 Offer 38. 字符串的排列 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 38. 字符串的排列 - 力扣（Leetcode）

题目的接口：

class Solution {
public:vector<string> permutation(string s) {}
};

解题思路：

知道题用到的是回溯的思想，

但是我之前没有做过回溯的题目，

所以可能在理解上有一点不太到位，请见谅：

我的思路是使用一个string来模拟每种情况，然后push进一个数组；

建一个类型是bool的数组用来判断字符串中的字符使用情况（哪个用了，哪个没用）；

为了更好的剪枝（删除重复情况），用排序将将相同的字母连在一起，

开始回溯：

如果情况成立，就push进数组；

通过循环遍历（以每个字符开始，有不同情况）

如果出现：同一层两个字符相等，且上一个字符用之前过，证明重复了（剪枝）

最后回溯完返回即可。

代码：

class Solution {
public://这是要返回的数组vector<string> res;vector<string> permutation(string s) {//判断字符串为空的情况if(s.size() == 0)   {return {};}//建一个string用来接收每种情况string tmp;//用这个数组来判断该位置有无字符（并初识化）vector<bool> used(s.size());//排序，将相同的字母连在一起sort(s.begin(), s.end());//回溯backtrack(s, tmp, used);//返回return res;}
private:void backtrack(string s, string& tmp, vector<bool>& used){//一种情况成立，push进resif(s.size() == tmp.size()){res.push_back(tmp);return;}//循环遍历每一个位置的每一种情况for(int i = 0; i < s.size(); i++){//如果该位置有字符了，就不进去，让i继续++if(!used[i]){//如果字符串s出现同一层两个字符相等，且上一个字符用之前过，证明重复了if(i >= 1 && s[i - 1] == s[i] && !used[i - 1]){continue;}//插入tmp.push_back(s[i]);//表示这个位置已经有字符了used[i] = true;//继续回溯backtrack(s, tmp, used);//返回上一层tmp.pop_back();//表示这个位置没有字符了（这样就能继续往tmp里面插入字符）used[i] = false;}}}
};

有很多题目思路很复杂，不可能只靠写一道题目就学会，

需要多去刷一些同类型的题目，才能更好的学习。