华为面试:给定一个只包含大写英文字母的字符串S,进行排列组合
程序员文章站
2024-03-18 10:34:10
...
import java.util.HashSet;
public class Arrange {
public static void main(String[] args) {
char[] chs = {'A','B','A'};
HashSet<String> set = new HashSet<String>();
arrange(chs, 0, chs.length,set);
System.out.print(set);
}
public static void arrange(char[] chs, int start, int len, HashSet<String> set) {
if (start == len - 1) {
String aString = "";
for (int i = 0; i < chs.length; ++i){
aString =aString +String.valueOf(chs[i]);
}
set.add(aString);
System.out.println();
return;
}
for (int i = start; i < len; i++) {
char temp = chs[start];
chs[start] = chs[i];
chs[i] = temp;
arrange(chs, start + 1, len, set);
temp = chs[start];
chs[start] = chs[i];
chs[i] = temp;
}
}
}
全排列:还是abc三个字符,全排列即字符不能重复。最后 3*2 =6种结果
可以利用1中的方法,只要判断3个字符是否相等,都不相等的才是需要的全排列里的一个。这样的时间复杂度为n^n,而全排列的种类为n!所以需要设计一种n!的算法。
也可以利用递归,第一个字符串一共有n种选择,剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择,都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换,得到n中情况,然后递归处理n-1的规模,只是处理完之后需要在换回来,变成原来字符的样子。