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

mpweixin用户普通 2024年4月3日下午3:27

List<List> res=new LinkedList<>();
List ans =new ArrayList<>();
void backtracking(TreeNode root,int tar) {
if(root null) return ;
ans.add(root.val);
tar-=root.val;
if (tar0&&root.leftnull &&root.rightnull) {
res.add(new ArrayList(ans));
}
backtracking(root.left,tar);
backtracking(root.right,tar);
ans.removeLast();
}
public List<List> pathTarget(TreeNode root, int target) {
backtracking(root,target);
return res;
}
思路：回溯模版

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月2日下午6:32

class Solution {

    List<String> res = new ArrayList<>();
    List<Character> path = new ArrayList<>();

    public String[] goodsOrder(String goods) {


        char[] arr = goods.toCharArray();
        boolean [] visited = new boolean [arr.length];
        Arrays.sort(arr);
        backTrace(arr,visited,0);

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

        return ss;
    }


    void backTrace(char[] arr,boolean [] visited, int index){
        // 对子集问题可以直接放进结果集里
        if(path.size()==arr.length){
            // res.add(new ArrayList<>(path));
            res.add(listToString(path));
            return;
        }

        for(int i = 0; i < arr.length; i++){
            // 去掉重复
            if(i > 0 && arr[i] == arr[i-1] && visited[i-1] == false){
                continue;
            }
            // 判断以前是否被访问过
            if(visited[i] == true){
                continue;
            }
            // 从多个元素中选一个
            path.add(arr[i]);
            visited[i]=true;
            // 递归
            backTrace(arr,visited,0);
            path.remove(path.size() - 1);
            visited[i]=false;
        }
    }

//List<Character> to String
    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 条回复

Jimmy 普通 2024年3月31日下午10:38

时间复杂度：O(n!n) 空间复杂度：O(n^2)

class Solution {
public:
    vector<char> path;
    vector<string> res;
    vector<string> goodsOrder(string goods) {
        vector<bool> visited(goods.size(),false);
        sort(goods.begin(),goods.end());
        dfs(goods,0,visited);
        return res;
    }

    void dfs(string& goods,int k, vector<bool>& visited)
    {
        if(k == goods.size())
        {
            res.push_back(string(path.begin(),path.end()));
        }
        for(int i=0;i<goods.size();i++)
        {
            if(i>0 && goods[i] == goods[i-1] && !visited[i-1])
            {
                continue;
            }
            if(!visited[i])
            {
                visited[i] = true;
                path.push_back(goods[i]);
                dfs(goods,k+1,visited);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月31日上午9:18

打卡

class Solution {
public:
    vector<string> goodsOrder(string goods) {
        if(goods.length() == 0) return {};
        vector<bool> used(goods.length(), false);
        sort(goods.begin(), goods.end());
        dfs(goods, used);
        return res;
    }
private:
    void dfs(string goods, vector<bool>& used) {
        if(tmp.length() == goods.length()) {
            res.emplace_back(tmp);
            return;
        }

        for(int i = 0; i < goods.length(); ++i) {
            if(used[i] || (i > 0 && goods[i] == goods[i - 1] && used[i - 1] == false)) continue;
            used[i] = true;
            tmp.push_back(goods[i]);
            dfs(goods, used);
            tmp.pop_back();
            used[i] = false;
        }
    }
private:
    string tmp;
    vector<string> res;
};

0 赞同 0 条回复

heathhou 普通 2024年3月30日下午10:18

class Solution {
public:
    vector<string> goodsOrder(string goods) {
        visited.resize(goods.size(), false);
        sort(goods.begin(), goods.end());

        dfs(0, goods);
        return res;
    }

    void dfs(int k,string& s){
        if(k == s.size()){
            res.push_back(string(path.begin(), path.end()));
            return;
        }

        for(int i = 0;i < s.size(); ++i){
            if(i > 0 && s[i] == s[i-1] && visited[i - 1] == false){
                continue;
            }
            if(!visited[i]){
                visited[i] = true;
                path.push_back(s[i]);
                dfs(k+1, s);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
private:
    vector<char> path;
    vector<string> res;
    vector<bool> visited;
};

时间复杂度：O(n * n!)
空间复杂度：O(n)

0 赞同 0 条回复

紫芝普通 2024年3月30日下午4:00

思路：回溯，每次交换当前位和string后续任一位置的值，如果该值已经被交换过了（即存在重复值），则跳过。在回溯算法中用一个变量记录当前所在位。

“`c++
class Solution {
public:
vector goodsOrder(string goods) {
dfs(goods, 0);
return ans;
}
private:
vector ans;
void dfs(string goods, int t) {
if (t == goods.size()-1) {
ans.push_back(goods);
return;
}
set used;
for (int i=t; i

0 赞同 0 条回复

王位詮釋普通 2024年3月29日下午10:21

自己写的，这种题一般就是用回溯法，一般如果给的是int类型数组且没有相同元素的话，我们可以直接进行递归获取全排列就行了，如果给的有重复元素，所以我们可以先给数组排序达到剪枝的效果，然后获取的时候判断当前访问元素是否和前一个相等，但是这里给的是字符串，所以我们可以先将字符串转换为字符数组，然后排序，这里我是直接用集合了，使用集合来天然去重。
class Solution {
    String goods;
    Set<String> result = new HashSet<>();
    public String[] goodsOrder(String goods) {
        this.goods = goods;
        boolean[] visited = new boolean[goods.length()];
        backtrace(new StringBuilder(),visited);
        return result.toArray(new String[0]);
    }
    public void backtrace(StringBuilder str,boolean[] visited){
        if(str.length()==goods.length()){
            result.add(str.toString());
            return;
        }
        for(int i=0;i<goods.length();i++){
            if(!visited[i]){
                visited[i] = true;
                str.append(goods.charAt(i));
                backtrace(str,visited);
                visited[i] = false;
                str.deleteCharAt(str.length()-1);
            }
        }
    }
}

0 赞同 0 条回复

方铎码农普通 2024年3月29日下午2:03

class Solution {
    List<String> 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，存储已经访问过的字母
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < arr.length; i++) {
            if(!set.contains(arr[i])){
                set.add(arr[i]);    //将已经访问了的内容放进set里
                swap(i,x);
                dfs(x+1);
                swap(x,i);
            } else {
                continue;
            }
        }
    }

    void swap(int a, int b){
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

时间复杂度$O(n)$，空间复杂度$O(n)$

0 赞同 0 条回复

云无深雁影普通 2024年3月29日上午10:35

class Solution {
public String[] goodsOrder(String goods) {
List ans = new ArrayList<>();
int sz = goods.length();
Boolean[] isUsed = new Boolean[sz];
for(int i = 0; i < sz; i++)
isUsed[i] = false;
return rec(isUsed,sz,goods).toArray(new String[sz]);
}
private List rec(Boolean[] isUsed,int left,String goods){
List total = new ArrayList<>();
HashSet set = new HashSet<>();
for(int i = 0; i < isUsed.length; i++){
if(!isUsed[i]){
isUsed[i] = true;
List temp = rec(isUsed,left – 1,goods);
for(String item :temp){
set.add(goods.charAt(i) +item);
}
if(temp.size() 0)
set.add(goods.charAt(i)+””);
isUsed[i] = false;
}
}
for(String s: set)
total.add(s);
return total;

}
//由于直接操作String 导致耗时较长。若需优化可以修改为回溯Integer序列
//时间复杂度O(n*n!)
//空间复杂度O(n2)

class Solution {
List ans =new ArrayList<>();
public String[] goodsOrder(String goods) {
Boolean[] visited = new Boolean[goods.length()];
for(int i = 0; i < goods.length();i++)
visited[i] = false;
dfs(visited,goods.length(),new StringBuilder(),goods);
return ans.toArray(new String[goods.length()]);

}
private void dfs(Boolean[] visited,int leftSize,StringBuilder sb,String goods){
    if(leftSize == 0){
        ans.add(sb.toString());
        return;
    }
    HashSet<Character> set = new HashSet<>();
    for(int i = 0; i < goods.length(); i++){
        if(set.contains(goods.charAt(i)) || visited[i])
            continue;
        set.add(goods.charAt(i));
        sb.append(goods.charAt(i));
        visited[i] = true;
        dfs(visited,leftSize-1,sb,goods);
        sb.deleteCharAt(sb.length()-1);
        visited[i] = false;
    }
}

}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复