题目
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
首先读题我们发现,这种从固定的数组/String 里的取出元素进行排列组合,是经典的permutation题目。然后我们发现,这题的要求是 需要我们返回所有不重复的排列组合,而不是返回有多少种排列组合,所以我们需要建一个String的Arraylist来存储所有排列出的不重复的字符串。
除此之外,我们新建一个辅助method,用于不停的循环向下寻找所有可能的排列组合。在这个辅助method里,有三个arguments。第一个是str,即当前我们剩下可以取的string,第二个是cur,即我们当前所拥有的字符串,第三个是result,是我们符合条件的字符串的合集。
在这个辅助method中,我们首先需要检测,我们还有没有能取的string,如果没有,我们便可以开始确认我们当前所拥有的字符串有没有被放进最后的Arraylist result中,如果没有,我们便将他加进去。接下来,当我们还有能取的string时,我们就可以开始进行循环。对于现在所剩下的string其中的每一个字符串,我们都将他尝试与我们现有的string cur进行组合,所以循环的argument的cur 此时变成cur+Str.charAt(i)。然后因为我们已经把当前位于i的字符取过了,我们的第一个argument需要被更新为除这个的剩下的string,我们这里运用了substring来取i之前的string和i之后的string进行相加。
如此循环,直到我们所有的可能性都被取完。
这个方法同样也适用于我们需要排列组合的时一个数组而非string的情况。
具体代码如下:
import java.util.ArrayList; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> result = new ArrayList<>(); if(str.length() == 0){ return result; } recur(str,"",result); return result; } public void recur(String str,String cur,ArrayList<String> result){ if(str.length() == 0){ if(!result.contains(cur)){ result.add(cur); } } for(int i = 0; i < str.length();i++){ recur(str.substring(0,i)+str.substring(i+1,str.length()),cur+str.charAt(i),result); } } }