《剑指offer》-字符串的排列
写在前面：
最近遇到了一道题涉及全排列的。记得之前在《剑指offer》上遇到了一道类似的题。因此今早把这道题翻了出来重新做一做，也趁这个机会重新学习一下全排列算法还有字典序排序算法。
题目：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：
这道题是一道典型的全排列然后在进行字典序排序的题。全排列的题目可以使用递归完成。其实，这道题的思想和分治也很像。假设咱们有字符串"abcd"，咱们可以先得出"cd"的全排列既["cd","dc"]，之后在此基础上分别求出"bcd"和"bdc"的全排列。以此类推。
这里涉及到一个问题，在求"bcd"和"bdc"的全排列的时候会有重复的问题，因此我们需要注意在写入最后总的数据结构的时候需要进行去重。
这道题最后还涉及到一个字典序排序的问题。Java的Collections类提供了sort方法，可以进行字典序排序。
代码：
/**
* Return all permutations of specified string.
* @param str
* @return
*/
public ArrayList<String> Permutation(String str) {
ArrayList<String>result = new ArrayList<String>();
if(str == null || str.length() == 0)
return result;
int size = str.length();
char [] chs = str.toCharArray();
all_permutations(result, chs, 0, size);
Collections.sort(result);
return result;
}
/**
* Find all permutations.
* @param result
* @param str
* @param i
* @param size
*/
private void all_permutations(ArrayList<String>result, char[] chs, int i, int size){
if(i == size){
String value = String.valueOf(chs);
if(!result.contains(value))
result.add(String.valueOf(chs));
}else{
for(int j=i;j<size;j++){
swap(chs, i, j);
all_permutations(result, chs, i + 1, size);
swap(chs, i, j);
}
}
}
/**
* Switching characters.
* @param i
* @param j
*/
private void swap(char [] chs, int i, int j){
char ch = chs[i];
chs[i] = chs[j];
chs[j] = ch;
}
题后思考：
做完这道题之后自己主要思考的是字典序排序的问题。虽然Collections.sort()可以很方便的解决字典序排序的问题但是过于的投机取巧。字典序的排序最好还是自己能够写一个出来。
字典序排序：
Arrays类有一个sort方法，咱们可以自定义其中的Comparator。好的，咱们现在的任务就是当有两个长度相同的字符串的时候，我们如何实现它们的字典序排序。
- 首先咱们需要忽略字母的大小写，这需要使用字符串的toLowerCase方法。
- 如果两个字符串的内容一致，则返回0。
- 如果第一个字符串小于第二个字符串（在小于的字符之前的所有字符都相等），则返回-1。
- 如果第一个字符串大于第二个字符串（在大于的字符之前的所有字符都相等），返回1。
代码：
Arrays.sort(ary, new Comparator<String>(){
public int compare(String o1, String o2) {
String[] temp = {o1.toLowerCase(), o2.toLowerCase()};
Arrays.sort(temp);
if(o1.equalsIgnoreCase(temp[0])){
return -1;
}else if(temp[0].equalsIgnoreCase(temp[1])){
return 0;
}else{
return 1;
}
}
});
Note：由于题目需要返回的是ArrayList类型，而字符串比较需要的是字符串数组类型。所以，我们需要先将ArrayList类型转换为字符串数组类型，再将字符串数组类型转换回ArrayList类型。转换代码如下所示：
//ArrayList类型转换为字符串数组类型
String[] array = (String[]) result.toArray(new String[0]);
//字符串数组类型转换回ArrayList类型
ArrayList<String>lists = new ArrayList<String>(Arrays.asList(array));
字典序排序的下一个字符串：
虽然之前写过字典序排序，但是Arrays.sort的方法本质上和Collections.sort()差不了太多。晚上上网查了查字典序排序的写法。给定一个字符串，如何求出该字符串按字典排序的下一个字符串。
思路：
我们观察一个字符串acdb，求出它的下一个字符串（字典序排序）。我们可以按照以下思路来解这道题。
- 找到第一个正序排序cd。
- 取正排序的第一个字符c的位置记为base。
- 从字符串的最后开始找大于c的字符（d）并记录其位置记为bigger。
- 交换base与bigger位置的字符我们得到adcb。
- 翻转bigger之后的字符，我们得到adbc。就是我们要的最终结果了。
代码：
public String permutation(char [] chs){
ArrayList<String>result = new ArrayList<String>();
char [] refs = chs;
int base = -1;
for(int i=chs.length - 1;i>1;i--){
if(chs[i] > chs[i-1]){
base = i-1;
break;
}
}
if(base == -1){
return null;
}
int bigger = 0;
for(int i=chs.length-1;i>=base;i--){
if(chs[i] > chs[base]){
bigger = i;
break;
}
}
swap(chs, base, bigger);
reverse(chs, base + 1, chs.length - 1);
return String.valueOf(chs);
}
private void swap(char [] chs, int i, int j){
char ch = chs[i];
chs[i] = chs[j];
chs[j] = ch;
}
private void reverse(char [] chs, int begin, int end){
while(begin < end){
swap(chs, begin, end);
begin++;
end--;
}
}
