【回溯专题】剑指 Offer 38. 字符串的排列-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年8月3日下午11:19

class Solution {

    private List<String> res;

    public String[] permutation(String s) {
        res = new ArrayList<>();
        char[] list = s.toCharArray();
        Arrays.sort(list);
        backTracking(new boolean[s.length()],String.valueOf(list),new StringBuilder());
        return res.toArray(new String[res.size()]);
    }

    private void backTracking(boolean[] visited,String s, StringBuilder curr){
        // 达到终止条件
        if(curr.length() == s.length()){
            res.add(curr.toString());
            return;
        }
        // 遍历集合，选择当前位置的元素
        for(int i = 0; i < s.length(); i ++){
            if(visited[i]){
                continue;
            }
            // 同一个位置只考虑一次重复元素中的一个
            if(i > 0 && s.charAt(i) == s.charAt(i-1) && !visited[i-1]){
                continue;
            }
            visited[i] = true;
            curr.append(""+s.charAt(i));
            backTracking(visited,s,curr);
            curr.deleteCharAt(curr.length()-1);
            visited[i] = false;
        }
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月19日下午1:49

class Solution {
    //全排列，每次都可以从0开始，选过的不能再选
    //没说有重复元素 但是测试用例有重复元素
    List<String> list = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    boolean[] used;

    public String[] permutation(String s) {
        used = new boolean[s.length()];
        //排序
        char[] ch = new char[s.length()];
        for(int i = 0; i < ch.length; i++){
            ch[i] = s.charAt(i);
        }
        Arrays.sort(ch);
        backTracing(ch);
        String[] res = new String[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
    void backTracing(char[] ch){
        if(path.length() == ch.length){
            list.add(path.toString());
            return;
        }
        for(int i = 0; i < ch.length; i++){
            if(i > 0 && ch[i] == ch[i - 1] && used[i - 1] == false) continue;
            if(used[i] == true) continue;
            path.append(ch[i]);
            used[i] = true;
            backTracing(ch);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月17日下午10:32

def permutation1(s: str) -> list[str]:
    result = []
    path = []
    visited = [False] * len(s)
    s = sorted(s)
    def dfs(arr,k):
        if k == len(arr):
            result.append("".join(path))
            return

        # 进行n叉树搜索（类似于二叉树搜索）
        # range(len(arr))相当于selectableStr
        for _ in range(len(arr)):
            # 如果已经访问过了
            if visited[_] == True:
                continue
            # 剪枝
            if _ > 0 and visited[_ - 1] == False and arr[_ - 1] == arr[_]:
                continue

            visited[_] = True
            path.append(arr[_])
            dfs(arr,k+1)
            visited[_] = False
            path.pop(-1)

    dfs(s,0)

0 赞同 0 条回复

lucca 普通 2023年1月16日下午8:51

无重复的全排列 DFS

时间复杂度 O(2^N)
空间复杂度 O(N)

class Solution {
    private char[] c, cs;
    private boolean[] vis;
    private List<String> li = new LinkedList<>();
    private int idx = 0;
    public String[] permutation(String s) {
        this.c = s.toCharArray();
        Arrays.sort(c);
        this.cs = new char[c.length];
        this.vis = new boolean[c.length];

        dfs(0);

        String[] ans = new String[li.size()];
        int idx = 0;
        for (String str : li) ans[idx++] = str;
        return ans;
    }

    private void dfs(int cur) {
        if (cur == c.length) {
            li.add(new String(cs));
            return;
        }

        for (int i = 0; i < c.length; i++) {
            if (i > 0 && c[i] == c[i - 1] && !vis[i-1]) continue;
            if (vis[i]) continue;
            vis[i] = true;
            cs[cur] = c[i];
            dfs(cur + 1);
            vis[i] = false;
        }
    }
}

0 赞同 0 条回复

@ 普通 2022年12月16日上午10:36

class Solution {
    List<Character> path;
    List<String> res;
    boolean[] visited;
    public String[] permutation(String s) {
        this.path = new ArrayList<>();
        this.res = new ArrayList<>();
        this.visited = new boolean[s.length()];

        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, 0);

        String[] ss = new String[res.size()];
        for(int i = 0; i < res.size(); i++){
            ss[i] = res.get(i);
        }

        return ss;

    }
    // 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
    void dfs(char[] arr, int k){
        if(arr.length == k){
           res.add(listToString(path));
           return;
        }

        //进行N叉树搜索
        for(int i = 0; i < arr.length; i++){
            // 剪枝 aab
            if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
                continue;
            }
            if(visited[i] == false){
                // 递归访问
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr, k + 1);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }

    String listToString(List<Character> list){
        StringBuilder b = new StringBuilder();
        for(int i = 0; i < list.size(); i++){
            b.append(list.get(i));
        }

        return b.toString();
    }
}

0 赞同 0 条回复

派大星普通 2022年12月2日下午10:58

class Solution {
//时间复杂度O(n)
    List<String> res;
    List<Character> path;
    boolean[] visited;
    public String[] permutation(String s) {
        this.res = new ArrayList<>();
        this.path = new ArrayList<>();
        //先转化为字符数组
        char[] c = s.toCharArray();
        visited = new boolean[s.length()];
        //将字符数组排序
        Arrays.sort(c);
        dfs(c,0);
        String[] ss = new String[res.size()];
        for(int i = 0; i < res.size(); i++){
            ss[i] = res.get(i);
        }

        return ss;
    }
    void dfs(char[] arr, int k){
        //arr所有元素都遍历完
        if(k == arr.length){
            res.add(toListString(path));
            return;
        }
        for(int i = 0;i < arr.length;i++){
            if(i > 0 && arr[i-1] == arr[i] && visited[i-1] == false) continue;
            if(visited[i] == false){
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr,k+1);
                visited[i] = false;
                path.remove(path.size()-1);
            }

        }

    }
    public String toListString(List<Character> path){
       StringBuilder b = new StringBuilder();
       for(int i = 0;i < path.size();i++){
           b.append(path.get(i));
       }
       return b.toString();
    }
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午10:46

class Solution {
public:
    vector<string> result;
    string path;
    void backtracking(string s, vector<bool>& used){
        if(path.size()==s.size()) {
            result.push_back(path);
            return;
        }
        for(int i = 0; i < s.size();i++){
            // if(i > startindex && s[i]==s[i-1]) continue;
            if(used[i] == true) continue; //为true则被使用过，跳过
            used[i] = true; //每次被用过后将置为true
            path.push_back(s[i]);
            backtracking(s, used);
            path.pop_back();
            used[i] = false;
        } 
    }
    vector<string> permutation(string s) {
        if(s.size()==0) return result;
        vector<bool> used(s.size(), false);
        sort(s.begin(),s.end());
        backtracking(s,used);
        set<string> res (result.begin(),result.end());
        vector<string> finalres;
        for(auto c: res){
            finalres.push_back(c);
        }
        return finalres;
    }
};

0 赞同 0 条回复

T 普通 2022年11月30日下午7:05

class Solution {
    List<String> res;
    boolean[] vis;
    public String[] permutation(String s) {
        int n = s.length();
        res = new ArrayList<>();
        vis = new boolean[n];
        char[] words = s.toCharArray();
        Arrays.sort(words);
        StringBuilder sb = new StringBuilder();
        backtrace(words, 0, n, sb);
        int size = res.size();
        String[] strs = new String[size];
        for(int i = 0; i < size; i++) {
            strs[i] = res.get(i);
        }
        return strs;
    }
    //index表示正在寻找第index个字母
    public void backtrace(char[] words, int index, int total, StringBuilder sb) {
        if(index == total) {
            res.add(sb.toString());
            return;
        }
        //循环遍历每一个字母
        for(int j = 0; j < total; j++) {
            //如果该字母被访问过或者和前面重复就跳过    
            if(vis[j] || (j > 0 && !vis[j - 1] && words[j-1] == words[j])) {
                continue;
            }
            vis[j] = true;
            sb.append(words[j]);
            backtrace(words, index + 1, total, sb);
            sb.deleteCharAt(sb.length() - 1);
            vis[j] = false;
        }

    }


}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月28日下午12:50

时间复杂度为O（n!n）,空间复杂度为O（n）

class Solution {
    List<String> res;
    List<Character> path;
    boolean[] visited;
    public String[] permutation(String s) {
        this.res = new ArrayList<>();
        this.path = new ArrayList<>();
        //先转化为字符数组
        char[] c = s.toCharArray();
        visited = new boolean[s.length()];
        //将字符数组排序
        Arrays.sort(c);
        dfs(c,0);
        String[] ss = new String[res.size()];
        for(int i = 0; i < res.size(); i++){
            ss[i] = res.get(i);
        }

        return ss;
    }
    void dfs(char[] arr, int k){
        //arr所有元素都遍历完
        if(k == arr.length){
            res.add(toListString(path));
            return;
        }
        for(int i = 0;i < arr.length;i++){
            if(i > 0 && arr[i-1] == arr[i] && visited[i-1] == false) continue;
            if(visited[i] == false){
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr,k+1);
                visited[i] = false;
                path.remove(path.size()-1);
            }

        }

    }
    public String toListString(List<Character> path){
       StringBuilder b = new StringBuilder();
       for(int i = 0;i < path.size();i++){
           b.append(path.get(i));
       }
       return b.toString();
    }
}

0 赞同 0 条回复

庄重普通 2022年11月24日下午6:22

// 思路：
//     1.对整个字符的全排列，需要注意重复的排列组合
//     2.先对字符串进行排序，方便进行剪枝
//     3.进行深度优先遍历，模拟出N叉树的形式
//     4.剪枝：同一层代表两个字符相同并且前一个字符处于为访问状态
//     5.递归操作，搜索到一个结果，插入容器，然后更改该路径的访问状态为false
//     6.循环操作
class Solution {
public:
    vector<string> permutation(string s) {
        visited = vector<bool>(s.size(),false);
        sort(s.begin(),s.end());
        dfs(s,0);
        return ret;
    }
private:
    void dfs(const string& s, int k){
        if(s.size() == k){
            ret.push_back(path);
            return;
        }
        //进行N叉树搜索
        for(int i = 0; i < s.size(); ++i){
            //剪枝
            if(i > 0 && s[i-1] == s[i] && visited[i-1] == false )
                continue;
            if(visited[i] == false){
                //递归访问
                visited[i] = true;
                path.push_back(s[i]);
                dfs(s,k+1);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
    vector<bool> visited;
    vector<string> ret;
    string path;
};
//时间复杂度O(nlogn*n!) sort排序nlogn 递归全排列n!
//空间复杂度O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月23日下午11:35

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    boolean[] used;
    public String[] permutation(String s) {
        //记录访问过的节点
        used = new boolean[s.length()];
        char[] temp = s.toCharArray();
        Arrays.sort(temp);
        dfs(temp,0);
        return res.toArray(new String[0]);
    }
    void dfs(char[] cs ,int depth){
        if(depth == cs.length){
            res.add(path.toString());
            return ;
        }
        for(int i = 0;i < cs.length;i++){
            if(used[i]) continue;//选取过的节点不使用
            //树层去重
            if(i > 0 && cs[i-1]==cs[i] && !used[i-1]) continue;
            path.append(cs[i]);
            used[i] = true;
            dfs(cs,depth+1);
            used[i] = false;
            path.deleteCharAt(path.length() - 1);
        }
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月23日下午3:10

public class Solution {
    private List<String> resultList;
    private List<Character> selectedCharacters;
    private boolean[] visited;

    /**
     * 回溯
     * 时间复杂度：O(n!n)
     * 空间复杂度：O(n)
     * */
    public String[] permutation(String s) {
        this.selectedCharacters = new ArrayList<>();
        this.resultList = new ArrayList<>();
        this.visited = new boolean[s.length()];

        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, 0);

        String[] result = new String[resultList.size()];
        for(int i = 0; i < resultList.size(); i++){
            result[i] = resultList.get(i);
        }

        return result;
    }

    void dfs(char[] arr, int k) {
        // 1. 满足条件则加入结果集
        if (arr.length == k) {
            resultList.add(listToString(selectedCharacters));
            return;
        }

        // 2. 遍历每个阶段的可选解集合
        for (int i = 0; i < arr.length; i++) {
            // 剪枝
            if(i > 0 && arr[i] == arr[i - 1] && !visited[i - 1]){
                continue;
            }

            if (!visited[i]) {
                // 选择此阶段其中一个解,将其加入到已选解集合中
                selectedCharacters.add(arr[i]);
                visited[i] = true;

                // 进入下一阶段
                dfs(arr, k+1);

                // 回溯
                selectedCharacters.remove(selectedCharacters.size()-1);
                visited[i] = false;
            }
        }
    }

    private String listToString(List<Character> list){
        StringBuilder stringBuilder = new StringBuilder();
        for (Character character : list) {
            stringBuilder.append(character);
        }
        return stringBuilder.toString();
    }
}

0 赞同 0 条回复

So 普通 2022年11月22日下午8:27

class Solution {
    List<Character> path;
    List<String> res;
    boolean[] visited;
    public String[] permutation(String s) {
        this.path = new ArrayList<>();
        this.res = new ArrayList<>();
        this.visited = new boolean[s.length()];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, 0);
        String[] ss = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ss[i] = res.get(i);
        }
        return ss;
    }

    void dfs(char[] arr, int k) {
        if (arr.length == k) {
            res.add(listToString(path));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i] == arr[i - 1] && !visited[i - 1]) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr, k + 1);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }

    String listToString(List<Character> list) {
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            b.append(list.get(i));
        }
        return b.toString();
    }
}

时间：O(n * n!)，空间：O(n)

0 赞同 0 条回复

Error 普通 2022年11月21日下午11:20

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []
        def dfs(x):
            if x == len(c) - 1:
                res.append(''.join(c))
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic:
                    continue
                dic.add(c[i])
                c[i], c[x] = c[x], c[i]
                dfs(x + 1)
                c[i], c[x] = c[x], c[i]
        dfs(0)
        return res

时间复杂度 O(log n)

0 赞同 0 条回复

【回溯专题】剑指 Offer 38. 字符串的排列

共以下 14 个回答

无重复的全排列 DFS

# 回答此问题取消回复

【回溯专题】剑指 Offer 38. 字符串的排列

共以下 14 个回答

无重复的全排列 DFS

# 回答此问题 取消回复

# 回答此问题取消回复