字符串排列

原创
2016/08/16 09:22
阅读数 54
  • 编写一个方法,确定某字符串的所有排列组合。给定一个string A和一个int n,代表字符串和其长度,请返回所有该字符串字符的排列,保证字符串长度小于等于11且字符串中字符均为大写英文字符,排列中的字符串字典序从大到小排序。(不合并重复字符串)
  • 测试样例:"ABC" 返回:["CBA","CAB","BCA","BAC","ACB","ABC"]
  • 首先是第一种方式:
import java.util.*;

public class Permutation {
    public ArrayList<String> getPermutation(String A) {
        ArrayList<String> res = new ArrayList<>();
		char [] arr = A.toCharArray();
		permutation(res, arr, 0);
        Collections.sort(res);
        Collections.reverse(res);
        return res;
    }
    
    public void permutation(ArrayList<String> res, char[] arr, int index){
        if(index == arr.length){
            res.add(String.valueOf(arr));
        	return;
        }        
        for(int i = index; i < arr.length; ++i){
            swap(arr, i, index);
            permutation(res, arr, index + 1);
            swap(arr, i, index);
        }
    }
    
    public void swap(char [] arr, int p, int q){
        char tmp = arr[p];
        arr[p] = arr[q];
        arr[q] = tmp;
    }
}
  • 下面这种是书上给出的解答,个人认为更加的清晰,只是空间复杂度稍微的高一些,还有就是string的链接需呀小号大量的时间:
public class getPerms {
    public static ArrayList<String> getPerms(String str){
        if(str == null)
            return null;
        ArrayList<String> res = new ArrayList<>();
        if(str.length() == 0) {
            res.add("");
            return res;//终止条件
        }
        char first = str.charAt(0);
        String next = str.substring(1);
        ArrayList<String> words = getPerms(next);
        for(String word : words){
            for(int i = 0; i <= word.length(); ++i){
                String s =insertCharAt(word, i, first);
                res.add(s);
            }
        }
        return res;
    }

    public static String insertCharAt(String s, int index, char c){
        String start = s.substring(0, index);
        String end = s.substring(index);
        return start + c + end;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部