给定字符串的全排列
字符串 排列 给定
2023-09-14 09:07:35 时间
描述
输入一个字符串,打印出该字符串的所有排列。例如,输入字符串”abc”,则输出有字符’a’,’b’,’c’所能排列出来的所有字符串”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。
解决方案
递归实现
从字符串中选出一个字符作为排列的第一个字符,然后对剩余的字符进行全排列。如此递归处理,从而得到所有字符的全排列。
/* * 参数arrayA:给定字符串的字符数组 参数start:开始遍历字符与其后面各个字符将要进行交换的位置 参数end:字符串数组的最后一位 * 函数功能:输出字符串数字的各个字符全排列 */ public void recursionArrange(char[] arrayA, int start, int end) { if (end < 1) return; if (start == end) { System.out.println(String.valueOf(arrayA)); } else { for (int i = start; i <= end; i++) { swap(arrayA, i, start); recursionArrange(arrayA, start + 1, end); swap(arrayA, i, start); } } } // 交换数组m位置和n位置上的值 public void swap(char[] arrayA, int m, int n) { if (m == n) { return; } char temp = arrayA[m]; arrayA[m] = arrayA[n]; arrayA[n] = temp; } public static void main(String[] args) { StringTest test = new StringTest(); String A = "abc"; char[] arrayA = A.toCharArray(); test.recursionArrange(arrayA, 0, arrayA.length - 1); }
代码优化点
其实end没有用到,可以去掉end,用 arrayA.length替代,省去了end作为入参。
回溯模板在此题的应用
性能不是很好,因为有contains()方法的存在,O(N)的复杂度。 但不失为一种模板思路。
List<List<Integer>> res = new LinkedList<>(); /* 主函数,输入一组不重复的数字,返回它们的全排列 */ List<List<Integer>> permute(int[] nums) { // 记录「路径」 LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; } // 路径:记录在 track 中 // 选择列表:nums 中不存在于 track 的那些元素 // 结束条件:nums 中的元素全都在 track 中出现 void backtrack(int[] nums, LinkedList<Integer> track) { // 触发结束条件 if (track.size() == nums.length) { res.add(new LinkedList(track)); return; } for (int i = 0; i < nums.length; i++) { // 排除不合法的选择 if (track.contains(nums[i])) continue; // 做选择 track.add(nums[i]); // 进入下一层决策树 backtrack(nums, track); // 取消选择 track.removeLast(); } }
public static void ss(String str) { ssH1(str.toCharArray(), new ArrayList<>()); } public static void ssH1(char[] chars, List<Character> tempList) { if (chars.length == tempList.size()) { String res = ""; for (Character character : tempList) { res += character; } strList.add(res); return; } for (int i = 0; i < chars.length; i++) { if (tempList.contains(chars[i])) { continue; } tempList.add(chars[i]); ssH1(chars, tempList); tempList.remove(tempList.size() - 1); } }
相关文章
- 常用的字符串截取方法
- String字符串转JSONArray
- 2022-11-01:给定一个只由小写字母和数字字符组成的字符串str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?
- 将字符串转换为date类型_java字符串转date类型
- mysql语句截取字符串_mysql分割字符串split
- fscanf读取一行字符串-语言文件操作
- gis经纬度坐标转换多格式兼容:支持字符串/数组/GeoJSON
- 2023-04-13:给定一个字符串数组strs,其中每个字符串都是小写字母组成的, 如果i < j,并且strs[i]和strs[j]所有的字符随意去排列能组
- Spring Boot 请求返回字符串中文乱码详解编程语言
- MySQL中字符串的分割算法(mysql字符串切割)
- 串利用Oracle中的拼接函数,快速合并多个字符串(oracle拼接多个字符)
- Linux下查找文件内容的关键字(linux查找文件字符串)
- ()函数的使用使用 Oracle 中的 LTRIM 函数去除字符串开头的空白(oracle中ltrim)
- asp实现检测字符串是否为纯字母和数字组合的函数
- C#生成随机字符串的实例
- C语言中字符串和数字的相互转换实现代码
- C字符串与C++中string的区别详解
- JS实现的用来对比两个用指定分隔符分割的字符串是否相同