题解 | #字符串的排列#

package org.example.test;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PerMutationTest {
    public static void main(String[] args) {
        PerMutationTest test = new PerMutationTest();
        System.out.println(JSONObject.toJSONString(test.doPerMutation1("abcde")));
    }

    ArrayList<String> ret = new ArrayList<>();

    public ArrayList<String> permutation(String str) {
        LinkedList<Character> chars = new LinkedList<>();
        doPerMutation(chars, str);
        return ret;
    }

    //回溯算法不能解决重复问题
    private void doPerMutation(LinkedList<Character> chars, String str) {
        if (chars.size() == 3) {
            StringBuilder r = new StringBuilder();
            for (Character c : chars) {
                r.append(c);
            }

            ret.add(r.toString());
            return;
        }
        for (char c : str.toCharArray()) {
            if (chars.contains(c)) {
                continue;
            }
            chars.add(c);
            doPerMutation(chars, str.substring(1));
            chars.removeLast();
        }
    }

    // dp公式：每次获取上次所以排列，然后再遍历上次排列，从头到尾插入字符串，形成新的字符串，并去重。
    private List<String> doPerMutation1(String str) {
        LinkedList<ArrayList<String>> dp = new LinkedList<>();
        int i = 0;
        for (char c : str.toCharArray()) {
            ArrayList<String> ret = new ArrayList<>();
            if (i >= 1) {
                List<String> last = dp.getLast();
                for (String s : last) {
                    for (int n = 0; n <= s.length(); n++) {
                        String s1 = s.substring(0, n) + c + s.substring(n);
                        if (!ret.contains(s1)) {
                            ret.add(s1);
                        }
                    }
                    dp.add(ret);
                }
            } else {
                ret.add(String.valueOf(c));
                dp.add(ret);
            }

            i++;
        }
        return dp.getLast();
    }
}