面试&笔试|笔试题（写出字符abc 的全排列（不重复）和所有组合）面试&笔试|Java

1、问题一：

给定一个字符串，满足正则表达式[a-zA-Z]+，打印这个字符串的全排列，结果顺序不限。例如，输入为abc，输出为：
【面试&笔试|笔试题（写出字符abc 的全排列（不重复）和所有组合）】abc acb bac bca cba cab

递归解法一：

import java.util.ArrayList; import java.util.List; public class LetterCombination { public static void main(String[] args){ String str = "abc"; List result = new ArrayList(); getAllLists(result,str,""); for(String each : result){ System.out.println(each); } } /** * @param base 以该字符串作为基础字符串，进行选择性组合。 * @param buff 所求字符串的临时结果 * @param result 存放所求结果 */ public static void getAllLists(List result, String base, String buff){ if(base.length() <= 0){ result.add(buff.toString()); } for(int i = 0; i < base.length(); i++){ getAllLists(result, new StringBuilder(base).deleteCharAt(i).toString(), buff + base.charAt(i)); } } }

递归解法二：

/** * Created by FHY on 2019/4/10. */ public class FullPermutationDemo { public static void main(String[] args){ String str = "aac"; List result = new ArrayList<>(); getAllList(result, str.toCharArray(), 0); for(String each : result){ System.out.println(each); } } public static void getAllList(List result, char[] strs, int begin){ if(begin == strs.length-1){ result.add(String.valueOf(strs)); } for(int i = begin; i < strs.length; i++){ swap(strs, i, begin); getAllList(result, strs, begin+1); swap(strs, i, begin); } }private static void swap(char[] strs, int index1, int index2) { char temp = strs[index1]; strs[index1] = strs[index2]; strs[index2] = temp; } }

有些公司的笔试题里面会继续问，如果以上字符串中有重复的字符，如何用尽量省时间和空间的方式，让输出的全排列没有重复？
答：我想到的思路是将解法一中：的List改为Set, 同时将ArrayList改为HashSet,这样保证了输出不重复的要求，附上改为Set后的代码：
答：解法二中，放入list中时，加上判断 :!result.contains(String.valueOf(strs))
2、问题二：
求输入字符串的全排列，如：输入"ABC"，输出：ABCABACBCABC
代码如下：

import java.util.ArrayList; import java.util.List; /** * Created by FHY on 2019/4/10. */ public class TestCombination { public static void main(String[] args){ String str = "ABC"; List result = new ArrayList(); StringBuilder sb = new StringBuilder(); char[] strs = str.toCharArray(); for(int i = 1; i<= strs.length; i++){ getCombination(str.toCharArray(), 0, i, result, sb); }}/** * @param strs 输入的字符串 * @param begin 从字符串中哪个元素选起 * @param len 本次组合的长度 * @param result 存放所有组合的集合 * @param sb 存放每一次已选择的元素 */ public static void getCombination(char[] strs, int begin, int len, List result, StringBuilder sb){if(len == 0){ result.add(sb.toString()); return; } if(begin >= strs.length) return; sb.append(strs[begin]); //选择第一个字符 getCombination(strs, begin + 1, len - 1, result, sb); //从剩下的n-1个字符中选择len-1个字符 sb.deleteCharAt(sb.length() - 1); // 取消选择第一个字符 getCombination(strs, begin + 1, len, result, sb); //从剩下的n-1个字符中选择len个字符。 } }