九号球普通 2023年12月1日下午9:04

“`java
//递归+剪枝
class Solution {
Set res;
List selected = new ArrayList<>();
boolean[] vis;
public String[] goodsOrder(String goods) {
if (goods == null || “”.equals(goods)) {
return new String[0];
}
char[] charArr = goods.toCharArray();
res = new HashSet();
vis = new boolean[charArr.length];
dfs(charArr);
String[] result = new String[res.size()];
int i = 0;
for (String str : res) {
result[i] = str;
i++;
}
return result;
}

void dfs(char[] arr) {
    if (selected.size() == arr.length) {
        StringBuilder sb = new StringBuilder();
        for (Character ch : selected) {
            sb.append(ch);
        }
        String str = sb.toString();
        res.add(str);
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        if (vis[i]) {
            continue;
        }
        selected.add(arr[i]);
        vis[i] = true;
        dfs(arr);
        selected.remove(selected.size() - 1);
        vis[i] = false;
    }
}

}

0 赞同 0 条回复

招舟子普通 2023年11月17日下午5:07

class Solution {
List path;
List res;
boolean[] visited;
public String[] goodsOrder(String goods) {
res = new ArrayList<>();
path = new ArrayList<>();
char[] arr = goods.toCharArray();

    visited = new boolean[arr.length];
    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(k==arr.length){
        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]){
        visited[i] =true;
        path.add(arr[i]);
        dfs(arr,k+1);
        path.remove(path.size()-1);
        visited[i] =false;
        }
    }
}
String listToString(List<Character> path){
    StringBuilder s  = new StringBuilder();
    for(int i=0;i<path.size();i++){
         s.append(path.get(i));
    }
    return s.toString();
}

}
递归+回溯
时间复杂度O(n^2)
空间复杂度O(n!n）

0 赞同 0 条回复

张开怀普通 2023年7月24日下午12:26

class Solution {
public:
    vector<string> permutation(string s) {
        vector<char> path;
        vector<string> res;
        vector<bool> visited(s.size(), false);

        sort(s.begin(), s.end());

        function<void(int)> dfs = [&](int k) {
            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]) {
                    continue;
                }
                if (!visited[i]) {
                    visited[i] = true;
                    path.push_back(s[i]);
                    dfs(k + 1);
                    path.pop_back();
                    visited[i] = false;
                }
            }
        };

        dfs(0);

        return res;
    }
};

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

0 赞同 0 条回复

BOZ 普通 2023年7月21日上午10:35

【思路】递归，做好剪枝即可
【复杂度】时间复杂度O(n!)，额外空间复杂度O(n)

class Solution {
    string tmp;
    vector result;
    char visited;

    void dfs(string &s, int idx, int num) {
        if (visited & (1 << idx)) return;

        // record current char
        tmp[num] = s[idx];
        visited |= (1 << idx);
        if (num == s.length() - 1) {
            result.push_back(tmp);
            visited &= ~(1 << idx);
            return;
        }

        // find next char
        int i = 0;
        while (i < s.length()) {
            // skip visited char
            while (visited & (1 << i) && i < s.length()) i++;
            if (i == s.length()) break;

            int k = i;
            dfs(s, i, num + 1);

            // branch cut
            while (s[i] == s[k] && i < s.length()) i++;
        }
        visited &= ~(1 << idx);
    }

public:
    vector permutation(string s) {
        // sort string
        std::sort(s.begin(), s.end());

        // begin dfs
        visited = 0;
        tmp.assign(s);
        int i = 0;
        while (i < s.length()) {
            int k = i;
            dfs(s, i, 0);

            // branch cut
            while (s[i] == s[k] && i < s.length()) i++;
        }
        return result;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:33

“`C++
void permutation(string& s, int start, vector& result) {
if (start == s.length() – 1) {
result.push_back(s);
return;
}

// 从当前位置开始，依次将后面的字符与当前位置交换，并递归生成后面的排列
for (int i = start; i < s.length(); ++i) {
    std::swap(s[start], s[i]);
    permutation(s, start + 1, result);
    std::swap(s[start], s[i]); // 还原字符位置，以便进行下一次交换
}

}

std::vector generatePermutations(std::string s) {
std::vector result;
permutation(s, 0, result);
return result;
}

“`

0 赞同 0 条回复

局外人普通 2023年7月19日下午8:07

思路：
时间复杂度：O(n!) 空间复杂度：O(n²)

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder track = new StringBuilder();
    boolean[] used;

    public String[] permutation(String s) {
        char[] word = s.toCharArray();
        Arrays.sort(word);
        used = new boolean[word.length];

        traverse(word);

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

        return list;

    }

    void traverse(char[] word){
        if(track.length()==word.length){
            res.add(track.toString());
            return;
        }

        for(int i=0; i<word.length; i++){
            if(used[i]) continue;

            if(i>0 && word[i]==word[i-1] && !used[i-1]) continue;

            track.append(word[i]);
            used[i] = true;

            traverse(word);

            track.deleteCharAt(track.length()-1);
            used[i] = false;
        }

    }
}

0 赞同 0 条回复

花老爷普通 2023年7月19日下午5:40

回溯

class Solution {
    private List<String> ans;

    public String[] permutation(String s) {
        boolean[] visited = new boolean[s.length()];
        ans = new ArrayList<>();
        char[] temp = s.toCharArray();
        Arrays.sort(temp);
        backtrack(0, new StringBuffer(), visited, temp);
        String[] ansArr = new String[ans.size()];
        for (int i = 0; i < ansArr.length; i++) {
            ansArr[i] = ans.get(i);
        }
        return ansArr;
    }

    private void backtrack(int len, StringBuffer sb, boolean[] visited, char[] s) {
        if (len == s.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] || (i > 0 && !visited[i-1] && s[i] == s[i-1])) {
                continue;
            }
            sb.append(s[i]);
            visited[i] = true;
            backtrack(len + 1, sb, visited, s);
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月17日下午6:50

排序，判断是否重复或者使用过该字符

 List<String> res = new ArrayList<>();
    StringBuffer sb = new StringBuffer();
    boolean[] used;
    public String[] permutation(String s) {
        int[] used = new int[s.length()];
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        backtracking(chars, used);
        return res.toArray(new String[0]);
    }
    public void backtracking(char[] chars, int[] used) {
        if(sb.length() == chars.length) {
            res.add(sb.toString());
            return;
        }
        for(int i = 0; i < chars.length; i++) {
            //排序后若有重复字符跳过，使用过的也跳过
            if(i > 0 && chars[i] == chars[i - 1] && used[i - 1] == 1 || used[i] == 1) {
                continue;
            }
            sb.append(chars[i]);
            used[i] = 1;
            backtracking(chars, used);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = 0;
        }
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月17日下午5:58

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);    //进行fds填充res集合，记录所有可能的结果

        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] == 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 条回复

Vow the vow。普通 2023年7月17日上午11:49

难

List<String> res = new ArrayList<>();
    List<Character> path = new ArrayList<>();
    boolean[] visited;
    public String[] permutation(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        visited = new boolean[n];
        dfs(arr, 0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(char[] arr, int depth){
        if(path.size() == arr.length){
            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]) continue;
            path.add(arr[i]);
            visited[i] = true;

            dfs(arr,depth+1);

            visited[i] = false;
            path.remove(path.size()-1);
        }
    }

    private String listToString(List<Character> path){
        StringBuilder s = new StringBuilder();
        for(char c : path){
            s.append(c);
        }
        return s.toString();
    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月17日上午6:41

class Solution:
    def permutation(self, s: str) -> List[str]:

        res = []
        cur = []
        visited = [0] * len(s)

        s = sorted(s)

        def backtrack():
            if len(cur) == len(s):
                res.append("".join(cur))
                return

            for i in range(len(s)):

                if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:
                    continue

                if visited[i] == 1:
                    continue

                visited[i] = 1
                cur.append(s[i])
                backtrack()
                cur.pop()
                visited[i] = 0

            return

        backtrack()
        return res

记得剪纸

0 赞同 0 条回复

yxy 普通 2023年7月16日下午8:51

复杂度O(n！)


class Solution {
    void backTrace(string& s, vector& res, string path)
    {
        if(path.size()==s.size())
        {
            res.push_back(path);
            return;
        }
        unordered_set us;
        for(int i=0;i0&&s[i]==s[i-1]&&s[i-1]!='#')
                continue;
            if(s[i]!='#')
            {
                char ch = s[i];
                s[i]='#';
                backTrace(s, res, path+ch);
                s[i] = ch;
            }
        }
    }
public:
    vector permutation(string s) {
        vector res;
        if(s.size()==0) return res;
        sort(s.begin(), s.end());
        string path;
        backTrace(s, res, path);
        return res;
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月16日下午3:56

MY

class Solution {
public:
    vector<string> ans;
    string temp;
    vector<bool> vis;
    vector<string> permutation(string s) {
        // 重复元素放到一块
        sort(s.begin(),s.end(),[](const char& c1,const char& c2){
            return c1<c2;
        });
        vis = vector<bool>(s.size(),false);
        dfs(s,0);
        return ans;
    }
    void dfs(string s,int idx){
        if(idx == s.size()){
            ans.push_back(temp);
            return;
        }
        for(int i=0;i<s.size();i++){
            if(!vis[i]){
                // 保证重复元素的相对顺序不变
                // 每次选择 第一个没被使用的重复元素
                //  a1  a2  b  选a时，如果a1没被用过，a2不能选
                if(i && s[i-1]==s[i] && !vis[i-1])
                    continue;
                vis[i] = true;
                temp += s[i];
                dfs(s,idx+1);
                vis[i] = false;
                temp.erase(temp.size()-1);
            }
        }
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月16日下午3:40

//时间复杂度 O(N!N) 空间复杂度O(N*N)
class Solution {
public:
    vector permutation(string s) {
        dfs(s, 0);
        return ans;
    }
private:
    vector ans;
    void dfs(string s, int x) {
        if(x == s.size() - 1) {
            ans.push_back(s);                       // 添加排列方案
            return;
        }
        set st;
        for(int i = x; i < s.size(); i++) {
            if(st.find(s[i]) != st.end()) continue; // 重复，因此剪枝
            st.insert(s[i]);
            swap(s[i], s[x]);                       // 交换，将 s[i] 固定在第 x 位
            dfs(s, x + 1);                          // 开启固定第 x + 1 位字符
            swap(s[i], s[x]);                       // 恢复交换
        }
    }
};

0 赞同 0 条回复

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

共以下 14 个回答

MY

# 回答此问题取消回复

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

共以下 14 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复