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

June 普通 2023年9月17日下午11:32

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

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

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

    return ans;
}

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] && vis[i-1] == false)
            continue;
        if(vis[i] == false)
        {
            vis[i] = true;
            path.add(arr[i]);
            dfs(arr, k+1);
            path.remove(path.size() - 1);
            vis[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 条回复

ppopp 普通 2023年9月10日下午12:48

class Solution {
public:
vector permutation(string s) {
dfs(s,0);
return res;
}

vector<string> res;
void dfs(string s, int cur){
    if(cur == s.size() - 1){  //现在已经是最后一个元素了，将排列方案添加至最后 
        res.push_back(s);
        return;
    }
    set<int> st; //申请一个集合容器
    for(int i = cur; i < s.size(); i++){
        if(st.find(s[i]) != st.end()) continue; //如果这个元素在，跳过
        st.insert(s[i]);  //集合插入s[i]
        swap(s[i], s[cur]);  //将s[i]固定在cur位
        dfs(s,cur+1);
        swap(s[i], s[cur]);                  
     }
}

};

0 赞同 0 条回复

Marshan 普通 2023年8月25日下午8:50

unordered_set去除重复元素

class Solution {
public:
    unordered_set<string> res;
    vector<bool> visited;
    string trace = "";
    vector<string> permutation(string s) {
        this->visited.resize(s.size(),false);
        backTrace(s,trace);
        return vector<string>(res.begin(),res.end());
    }
    void backTrace(string& s,string& trace){
        if(trace.size() == s.size()){
            res.insert(trace);
            return;
        }
        for(int i = 0;i < s.size();++i){
            if(visited[i]){
                continue;
            }
            trace.push_back(s[i]);
            visited[i] = true;

            backTrace(s,trace);

            visited[i] = false;
            trace.pop_back();
        }
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午12:24

//回溯+dfs   全排列去重问题
class Solution {
    private Set<String> res;
    private StringBuilder cur;

    public String[] permutation(String s) {
        res = new HashSet<>();
        cur = new StringBuilder();
        boolean[] used = new boolean[s.length()];
        dfs(s, 0, used);


        return res.toArray(new String[res.size()]);
    }

    public void dfs(String s, int curIndex, boolean[] used) {
        if(cur.length()==s.length()) {
            res.add(new String(cur));
            return;
        }

        for(int i=0;i<s.length();i++) {
            if(!used[i]) {
                cur.append(s.charAt(i));
                used[i] = true;
                dfs(s, i+1, used);
                used[i] = false;
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }
}

0 赞同 0 条回复

Mby 普通 2023年8月14日下午1:15

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^2)
    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();
        //时间复杂度：O(n!n)
        //空间复杂度：O(n^2)
    }
}

0 赞同 0 条回复

北辰普通 2023年8月13日上午12:26

class Solution {
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        boolean[] visited = new boolean[chars.length];
        String str = "";
        int k= chars.length;
        List<String> res = new ArrayList<>();
        dfs(chars,visited,str,k,res);
        Set<String> set = new HashSet<>();
        for(int i=0;i<res.size();i++) set.add(res.get(i));
        String[] result = new String[set.size()];
        int l=0;
        for(String item:set) {
            result[l++]=item;
        }
        return result;
    }

    private void dfs(char[] chars, boolean[] visited, String str, int k, List<String> res) {
        if(str.length()==k) {
            res.add(str);
            return;
        }
        for(int i=0;i<chars.length;i++) {
            if(visited[i]==true) {
                continue;
            }
            visited[i]=true;
            str = str+chars[i];
            dfs(chars,visited,str,k,res);
            String temp = "";
            for(int j=0;j<str.length()-1;j++) {
                temp+=str.charAt(j);
            }
            str = temp;
            visited[i]=false;
        }
    }
}

时间复杂度：O（n!）

0 赞同 0 条回复

CaCO3 永久会员 2023年8月10日下午4:19

”’java
class Solution {
List result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public String[] permutation(String s) {
boolean[] visited = new boolean[s.length()];
char[] ch = s.toCharArray();
Arrays.sort(ch);
s = new String(ch);
backTracking(s,0,visited);
return result.stream().toArray(String[]::new);
}
public void backTracking(String s,int startIndex,boolean[] visited){
if(sb.length() s.length()){
result.add(sb.toString());
return;
}
for(int i = 0;i < s.length();i++){
//是否访问过
if(visited[i] || (i >= 1 && !visited[i-1] && s.charAt(i-1) s.charAt(i))){
continue;
}
sb.append(s.charAt(i));
visited[i] = true;
backTracking(s,i+1,visited);
sb.deleteCharAt(sb.length()-1);
visited[i] = false;
}
}
}
”’

0 赞同 0 条回复

#00456B 普通 2023年8月10日上午12:28

class Solution {
public:
    vector<string> ans;
    string path;//排列的过程中记录一条排列路径

    vector<string> permutation(string s) {
        sort(s.begin(), s.end());//排序
        vector<bool> visited(s.size(), false);//记录是否访问过
        dfs(s, visited);
        return ans;
    }

    void dfs(string s, vector<bool> visited){
        //说明找到了一组结果
        if(path.size() == s.size()){
            ans.push_back(path);
            return ;
        }

        for(int i = 0; i < s.size(); i++){
            /*
            //visited[i - 1] == true, 说明在同一个树枝上s[i-1]被用过
            //visited[i - 1] == false, 说明在同一层上s[i - 1]被用过，因为已经排序过了，当s[i] == s[i - 1] && visited[i - 1] == false时表示一定是前面已经出现过了
            //如果同一层上s[i - 1]被用过就直接跳过
            //例如[1, 1, 2]
            //   [1,1,2]11
            //    /  |  \
            //   1   1   2
            //   O   X   O //第二个1因为在同一层中出现过，所以在这里应该被舍去
            //  / \ / \ / \
            //  1 2 1 2 1 1
            //  | | | | | |
            //  2 1 2 1 1 1
            */
            if(i > 0 && s[i] == s[i - 1] && visited[i - 1] == false){
                continue;
            }
            if(visited[i] == false){
                visited[i] = true;
                path.push_back(s[i]);
                dfs(s, visited);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月7日下午5:32

class Solution {

 ArrayList<String> result=new  ArrayList<String>();
 StringBuffer path=new StringBuffer();
 int user[]=new int[10];
public String[] permutation(String s) { 
   String s1[]=s.split("");
   Arrays.sort(s1);
   balc(s1);
   String[] result1=new String[result.size()];
   for(int i=0;i<result1.length;i++)
   {
       result1[i]=result.get(i);
   }
   return result1;

}
public void balc(String [] s1)
{
    if(path.length()==s1.length)
    {
        result.add(new String(path));
        return;
    }

    for(int i=0;i<s1.length;i++)
    {
        //同一层 用过了 要剪枝
        if(i>0&&user[i-1]==0&&s1[i].equals(s1[i-1]))
        {
            continue;
        }
        if(user[i]==1)
        {
            continue;
        }else{


        user[i]=1;
        path.append(s1[i]);
        balc(s1);
        user[i]=0;
        path.deleteCharAt(path.length()-1);
        }
    }
}

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月4日下午11:39

8.4
Day25：下面是代码

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        //res.size()来获取元素数量
        return res.toArray(new String[res.size()]);
    }

    public void dfs(int x){
        if(x == c.length - 1){
            res.add(String.valueOf(c));
            return;
        } 
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++){
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }
    public void swap(int a, int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp; 
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月4日下午7:11

//排列
class Solution {
    List<String> result = new ArrayList<>();
    boolean[] flag;
    public String[] permutation(String s) {
        flag = new boolean[s.length()];
        StringBuilder path = new StringBuilder();
        progress(s, path);

        return result.toArray(new String[result.size()]);
    }

    public void progress(String s, StringBuilder path){
        if(path.length() == s.length()){
            result.add(path.toString());
            return;
        }

        Set<Character> set = new HashSet<>();
        for(int i = 0; i < s.length(); i++){
            if(flag[i] == true || set.contains(s.charAt(i))) continue;
            flag[i] = true;
            set.add(s.charAt(i));
            path.append(s.charAt(i));
            progress(s, path);
            path.deleteCharAt(path.length() - 1);
            flag[i] = false;
        }

    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月4日下午3:26

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        boolean[] visited = new boolean[s.length()];
        backTracking(chars,visited);
        return res.toArray(new String[res.size()]);
    }

    public void backTracking(char[] chars, boolean[] visited) {
        // 边界
        if(sb.length() == chars.length) {
            res.add(sb.toString());
            return ;
        }
        for(int i = 0 ; i < chars.length ; i ++) {
            if(visited[i]) continue;
            // 去重
            if(i > 0 && chars[i] == chars[i-1] && visited[i-1]) continue;
            // 逻辑
            sb.append(chars[i]);
            visited[i] = true;
            // 回溯
            backTracking(chars,visited);
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

0 赞同 0 条回复

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

共以下 12 个回答

# 回答此问题取消回复

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

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复