动态规划-字符串的排序

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
来源：牛客网

字符串的排序
解题思路：1.前求出所有的字符串 2.再进行字典序排序3.再去重
1.求出所有的字符串---动态规划思想
abc的全排列是在ab的全排列结果【“ab”，“ba”】的基础上增加c得到
拿ab举例：ab 的长度为2，则c由三个位置，分别为0,1,2来插入到“ab”中
此时将c的位置用j表示，“ab”用s表示，则新的字符串str=s.substring(0,j)+c+s.substring(j,s.length());
这样可以用几乎遍历的方式求出所有的字符串
2.利用HashSet进行去重
HashSet set=new HashSet(ret_new);
ret_new.clear();
ret_new.addAll(set);
3.利用sort方法进行字典序排序
Collections.sort(ret_new);
最后整体的java实现代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> ret=new ArrayList();
        int n=str.length();
        if(n==0) return ret;
        ret.add(str.substring(0,1));
        for(int i=1;i<n;i++){
            ArrayList<String> ret_new=new ArrayList();
            for(String s:ret){
//                 char ch=(char)str.indexOf(i);
                for(int j=0;j<=s.length();j++){
                    String tmp=s.substring(0,j)+str.substring(i,i+1)+s.substring(j,s.length());
                    ret_new.add(tmp);
                }
            }
            HashSet set=new HashSet(ret_new);
            ret_new.clear();
            ret_new.addAll(set);
            Collections.sort(ret_new);
            ret=ret_new;
        }
        return ret;
    }
}