字符串排列

Dear 丶 2021-09-22 06:20 321阅读 0赞

在网上看到了一个操作字符串的题目，该题为：字符串排列。大概意思是列出字符串中所有字符的所有组合并且输出无重复。自己做了一下，这里分享该题的思路，和做法。（自我觉得实现的有些麻烦）。欢迎指点。  
问题

输入一个字符串,打印出该字符串中字符的所有排列。

输入：

字符串abc。

输出：

打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

字符串abc的所有排列存在三种情况：  
1、以a开始，再连接bc的所有排列；  
2、以b开始，再连接ac的所有排列；  
3、以c开始，在连接ab的所有情况。  
然后在计算长度为2的字符串的所有排列，方法如上。所以采用递归的方式,递归直至字符串长度为2时。当长度为2时，字符串的排列一种为字符串正序，另一种为字符串的反序。长度为4或以上的也是如此。

![这里写图片描述][SouthEast]  
public static ArrayList Permutation(String str) \{  
// 存储每一次递归的结果  
ArrayList result = new ArrayList<>();

// 如果参数为空或者长度为0 不计算并且返回空
    	if (str == null || str.length() == 0) {
    		return null;
    	}
    
    	// 如果参数长度为1 那么所有的排列就是自身
    	if (str.length() == 1) {
    		result.add(str);
    		return result;
    	}
    
    	// 如果参数长度为2就调用基准情况（递归终止条件）
    	if (str.length() == 2) {
    		return Permutation2(str);
    	}
    	for (int i = 0; i < str.length(); i++) {
    		String strTemp = str.substring(0, i) + str.substring(i + 1, str.length());
    		if (!"".equals(strTemp)) {
    			ArrayList<String> array = Permutation(strTemp);
    			for (int j = 0; j < array.size(); j++) {
    				result.add(str.charAt(i) + array.get(j));
    			}
    		}
    	}
    
    	// 去除重复的排列
    	ArrayList<String> aa = new ArrayList<>();
    	for (int i = 0; i < result.size(); i++) {
    		if (!aa.contains(result.get(i))) {
    			aa.add(result.get(i));
    		}
    	}
    	return aa;
    }
    
    /**
     * 递归的基准情况。
     * 
     * @param str
     *            参数长度为2
     * @return 长度为2的字符串的所有可能排列，即自身和反序
     */
    public static ArrayList<String> Permutation2(String str) {
    	ArrayList<String> result = new ArrayList<>();
    	if (str.charAt(0) == str.charAt(1)) {
    		result.add(str);
    	} else {
    		result.add(str.charAt(0) + "" + str.charAt(1));
    		result.add(str.charAt(1) + "" + str.charAt(0));
    	}
    	return result;
    }

[SouthEast]: /images/20210920/326e6cfa47fa4bb1967f7d2a41f15815.png