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

陆狗陆狗普通 2024年12月25日上午1:33

解题思路
– 把字符串转换成字符数组
– 把问题转换成排列组合，只是需要额外考虑下字符重复的问题
【题解1】错误的写法，没有考虑到goods=”aab”，字符重复了就不能用了，但是基本思路是没有问题的

class Solution {

    char[] chars;
    List<String> result = new ArrayList();
    // 【错误1】:Set是无序的
    List<Character> selectChar = new ArrayList();

    public String[] goodsOrder(String goods) {
        // 把字符串转成字符数组
        chars = goods.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            dfs(chars[i]);
        }
        return result.toArray(new String[0]);
    }

    public void dfs(char nextChar) {
        // 当前要加入的字符是否已经被选择了
        // 【错误写法】goods="aab"，字符重复了就不能用了
        if (selectChar.contains(nextChar)) {
            return;
        }

        // 选择的已经完毕
        if (selectChar.size() == chars.length - 1) {
            result.add(toString(selectChar) + nextChar);
            return;
        }

        // 未被选择
        selectChar.add(nextChar);
        for (int i = 0; i < chars.length; i++) {
            dfs(chars[i]);
        }
        // 【错误点2】要移除最后一个（这一步就是回溯的实现）
        selectChar.removeLast();
    }

    public String toString(List<Character> charSet) {
        StringBuilder sb = new StringBuilder();
        for (Character c : charSet) {
            sb.append(c);
        }
        return sb.toString();
    }
}

错误点1：最开始用的是Set，但是Set是无序的
错误点2：要移除最后一个（这一步就是回溯的实现）
【题解2】改进版,能够ac，借助用数组去标识是否已经访问过

class Solution {

    char[] chars;
    List<String> result = new ArrayList();
    // 【改进】:用数组去标识是否已经访问过
    boolean[] used;

    public String[] goodsOrder(String goods) {
        // 把字符串转成字符数组
        chars = goods.toCharArray();
        Arrays.sort(chars);
        used = new boolean[chars.length];

        for (int i = 0; i < chars.length; i++) {
            dfs(new ArrayList(), i);
        }
        return result.toArray(new String[0]);
    }

    public void dfs(List<Character> selectChar, int i) {
        // 剪枝条件 1：当前要加入的字符是否已经被选择了
        if (used[i]) {
            return;
        }

        // 【改进】剪枝条件 2：当前字符和前一个字符相同，且前一个字符未被使用，跳过重复选择
        // 作用就是，先通过Arrays.sort(chars);排序数组，然后通过!used[i - 1]保证了重复数据只能按照一个固定的顺序a1，a2，a3的方式被使用
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
            return;
        }

        // 选择的已经完毕
        if (selectChar.size() == chars.length - 1) {
            result.add(toString(selectChar) + chars[i]);
            return;
        }

        // 未被选择
        selectChar.add(chars[i]);
        used[i] = true;
        for (int j = 0; j < chars.length; j++) {
            dfs(selectChar, j);
        }
        // 【错误点2】要移除最后一个（这一步就是回溯的实现）
        selectChar.removeLast();
        used[i] = false;
    }

    public String toString(List<Character> charSet) {
        StringBuilder sb = new StringBuilder();
        for (Character c : charSet) {
            sb.append(c);
        }
        return sb.toString();
    }
}

改进点1：用数组去标识是否已经访问过
改进点2：当前字符和前一个字符相同，且前一个字符未被使用，跳过重复选择

【题解2】参考题解，借助char[] chars比如abc，其中a已经被使用了，那么只需要排列b和c的关系即可

class Solution {

    char[] chars;
    List<String> result = new ArrayList();

    public String[] goodsOrder(String goods) {
        chars = goods.toCharArray();
        dfs(0);
        return result.toArray(new String[result.size()]);
    }

    // x表示当前属于第几层
    public void dfs(int x) {
        // 剪枝条件1：到达倒数第一层
        if (x == chars.length - 1) {
            result.add(new String(chars));
            return;
        }

        Set<Character> existed = new HashSet();
        // i表示当前层次x下，还可以变动的次数（因为前面x-1层的数据是确定的，只剩下chars.length-1-x个数据可以选择了 ）
        for (int i = x; i < chars.length; i++) {
            if (existed.contains(chars[i])) {
                // 【改进点2】剪枝条件2：当前层已经存在相同值的元素
                continue;
            }
            existed.add(chars[i]);
            // 交换
            // 【改进点1】通过交换实现chars数组的复用
            swap(chars, x, i);
            // 下一层
            dfs(x + 1);
            // 交换回来（回溯）
             // 【改进点1】通过交换回来实现回溯
            swap(chars, i, x);
        }
    }

    public void swap(char[] chars, int m, int n) {
        char tmpt = chars[m];
        chars[m] = chars[n];
        chars[n] = tmpt;
    }

}

回溯的核心思想1，可以复用一个数组或者链表，一般是操作1—》dfs（下一层）—》操作1的逆向操作
- 因此可以做到同一层dfs里面的循环多次前后数组的数据是不变的，循环的任意两个i和j的顺序是可以互换的等价的，唯一的区别是不同循环i和j，fix+i 和fix+j的区别
- 下一层执行前后的数组或者链表的数据是不变的，下一层前是fix+i，下一层后还是fix+i。
回溯的核心思想2，上一层的东西是固定的不变的fix，本层只关心本层及下一层

0 赞同 0 条回复

秋山丽奈普通 2024年12月21日下午3:49

思路：递归处理使用HashSet 处理重复问题

class Solution {

    boolean[] flag;
    HashSet<String> ans = new HashSet<>();
    List<String> temp;
    int index = 0;
    public String[] goodsOrder(String goods) {
        String[] goodList = goods.split("");
        int len = goodList.length;
        temp = new ArrayList<String>();
        flag = new boolean[len];

        build(goodList, 0, len);
        return ans.toArray(new String[0]);
    }

    public void build(String[] goodList, int count, int len){
        if(count == len){
            // 填充完成 
            String currentAns = "";
            for(String current: temp){
                currentAns += current;
            }
            ans.add(currentAns);

            return;
        }

        for(int i = 0; i < len; i ++){
            if(!flag[i]){
                // 当前 未被使用 
                flag[i] = true;
                temp.add(goodList[i]);
                build(goodList, count+1, len);
                temp.remove(temp.size()-1);
                flag[i] = false;
            }
        }
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月19日下午7:15

dfs解法

class Solution {
    char[] arr;
    List<String> res;
    public String[] goodsOrder(String goods) {
        arr=goods.toCharArray();
        res=new ArrayList<>();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    public void dfs(int x){
        if(x==arr.length-1){
            res.add(String.valueOf(arr));
        }

        Set<Character> set=new HashSet<>();
        for(int i=x;i<arr.length;i++){
            if(set.contains(arr[i])) continue;
            set.add(arr[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }


    public void swap (int i,int j){
        char temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月19日下午4:41

class Solution {
public:
    vector<string> res;
    char pre;
    vector<string> goodsOrder(string goods) {
        dfs(goods, 0);
        return res;
    }
    void dfs(string goods, int k) {
        if(k == goods.size() - 1) {
            res.push_back(goods);
            return;
        }
        set<char> st;
        for(int i = k; i < goods.size(); i++) {
            if(st.find(goods[i]) != st.end()) {
                continue;
            }
            st.insert(goods[i]);
            swap(goods[i], goods[k]);
            dfs(goods, k + 1);
            swap(goods[i], goods[k]);
        }
    }
};

优先深度搜索，通过交换字符串位置得到所有排列，通过set来判断是否重复。
时间复杂度O(N!∗N)，空间复杂度O(N)。

0 赞同 0 条回复

苯庸普通 2024年12月19日上午11:26

class Solution {
boolean[] visited;
Set res = new HashSet();
public String[] goodsOrder(String goods) {
visited = new boolean[goods.length()];
dfs(goods, new StringBuilder());
return res.toArray(new String[0]);
}

void dfs(String str, StringBuilder sb){
    if(sb.length() == str.length()){
        res.add(sb.toString());
        return;
    }
    for(int i = 0; i < str.length(); i++){
        if(!visited[i]){
            sb.append(str.charAt(i));
            visited[i] = true;
            dfs(str, sb);
            sb.deleteCharAt(sb.length()-1);
            visited[i] = false;
        }   
    }

}

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

月下足迹普通 2024年12月19日上午10:43

class Solution {
List res = new LinkedList<>();
char[] arr;
public String[] goodsOrder(String goods) {
arr = goods.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x arr.length – 1) {
res.add(String.valueOf(arr)); // 添加排列方案
return;
}
HashSet set = new HashSet<>();
for(int i = x; i < arr.length; i++) {
if(set.contains(arr[i])) continue; // 重复，因此剪枝
set.add(arr[i]);
swap(i, x); // 交换，将 arr[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}

0 赞同 0 条回复

Jerry 普通 2024年12月18日下午8:43

class Solution {
public:
    vector<string> res;
    set<string> record;
    vector<string> goodsOrder(string goods) {
        string oneres;
        vector<int> valid(goods.size(), 1);
        dfs(goods, oneres, valid);
        return res;
    }
    void dfs(string& goods, string& oneres, vector<int>& valid){
        if(oneres.size() == goods.size()){
            if(record.count(oneres) != 0) return;
            res.push_back(oneres);
            record.insert(oneres);
            return;
        }
        for(int i = 0; i < goods.size(); i++){
            if(valid[i] == 0) continue;
            char c = goods[i];
            valid[i] = 0;
            oneres.push_back(c);
            dfs(goods, oneres, valid);
            oneres.pop_back();
            valid[i] = 1;
        }
        return;
    }
};

注意点：刚开始没有加set类型的record判断重复，导致用例“aab”无法通过。

0 赞同 0 条回复

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复