剑指offer38 字符串的排列

发表于 | 分类于 |
字数统计: 238 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

题意

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

解法

同全排列 递归每次进行交换
复习一下swap的写法
由于题目中存在相同字母的情况，因此需要进行判断是否存在相同的字符
如果相同则不进行交换
保证出现的答案中不会产生重复

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> ans;
    void dfs(string s, int loc) {
        if (loc == s.size()) {
            ans.push_back(s);
            return;
        }
        int n = s.size();
        
        for (int i = loc; i < n; i++) {
            bool flag = true;
            for (int j = loc; j < i; j++) {
                if (s[i] == s[j]) { // 如果位置i之前存在相同的字母 就不用进行交换
                    flag = false; // 进行剪枝
                }
            }
            if (flag) {
                swap(s[i], s[loc]);
                dfs(s, loc + 1);
                swap(s[i], s[loc]);
            }
        }

    }
    vector<string> permutation(string s) {
        dfs(s, 0);
        return ans;
    }
};