每日算法之字符串的排列
2023-03-31 10:42:09 时间
JZ38 字符串的排列
描述
输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
题目主要信息
给定一个长度为n的字符串,求其中所有字符的全排列
字符串中可能有重复字符,打印顺序任意
字符串中只包含大小写字母
思路
都是求元素的全排列,字符串与数组没有区别,一个是数字全排列,一个是字符全排列。为了便于去掉重复情况,还是参照数组全排列,优先考虑字典序排序,因为排序后重复的字符就会相邻,后序递归找起来也很方便
使用临时变量去组装一个全排列情况:每当我们选取一个字符以后,就确定了其位置,相当于对字符串中剩下的元素进行全排列添加在该元素的后面,给剩余部分进行全排列就是一个子问题,因此可以使用递归。
终止条件:临时字符串中选取了n个元素,已经形成了一种排列情况,可以将其加入输出数组中。
返回值:每一层给上一层返回的就是本层级在临时字符串中添加的元素,递归到末尾的时候,就能添加全部元素
具体做法
先对字符串按照字典序排序,获得第一个排列情况
准备一个空串,暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了
每次递归从头遍历字符串,获取字符加入:首先根据vis数组,已经加入的元素不能再加入了;同时,如果当前的元素str[i]与同一层的前一个元素str[i-1]相同,且str[i-1]已经用,也不需要将其加入
进入下一等递归前将vis数组当前位置标记为使用过
回溯时,需要修改vis数组当前位置标记,同时去掉刚刚加入的字符串元素
临时字符串长度达到原串长度就是一种排列情况
代码
package mid.JZ38字符串的排列;
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private StringBuilder builder = new StringBuilder();
private ArrayList<String> res = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if (str == null || str.length() == 0) {
return res;
}
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sortedStr = new String(chars);
//当vis[i]=0,表示index为0的字符没有被使用
//当vis[i]=1,表示index为1的字符被使用了
int[] vis = new int[chars.length];
dfs(sortedStr, vis, 0);
return res;
}
private void dfs(String str, int[] vis, int depth) {
if (builder.length() == str.length()) {
res.add(builder.toString());
return;
}
for (int i = 0; i < str.length(); i++) {
if (vis[i] == 1) {
continue;
}
//当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
if (i != 0 && str.charAt(i) == str.charAt(i - 1) && vis[i - 1] == 1) {
continue;
}
builder.append(str.charAt(i));
vis[i] = 1;
dfs(str, vis, depth + 1);
builder.deleteCharAt(builder.length() - 1);
vis[i] = 0;
}
}
public static void main(String[] args) {
System.out.println(new Solution().Permutation("ab"));
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十