剑指 Offer 38. 字符串的排列 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:12
浏览次数:4
分类:技术文章
本文共 1739 字,大约阅读时间需要 5 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 这道题又是相当经典, 这里提供一种非常通用的方法供大家参考, 它还能解决类似的问题, 比如数字的排列, 也不用考虑有重复元素的情况
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
1 <= s 的长度 <= 8
题目样例
示例
输入:s = “abc”
输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]题目思考
- 如何不重复地得到所有排列?
解决方案
思路
- 要想不重复地得到所有排列, 我们可以定义一个方法, 来求字典序的下一个排列, 正如题目示例中的输出数组的顺序那样
- 初始化为最小的字典序, 然后当遍历到最大的字典序的时候, 就说明所有排列都被找到了
- 所以算法的核心就是如何通过一个字符串找它的字典序的下一个排列
- 下一个排列一定是所有排列中大于当前字符串且最接近它的, 所以我们可以利用贪心算法, 具体步骤如下:
- 从后向前找第一个小于后一个字符的字符 i (因为如果大于等于后一个字符的话, 就没法与后面的字符交换来使得整体字符串更大了)
- 找刚才遍历的部分的大于且最接近 i 的字符 j
- 将它们两个互换
- 然后 i 往后的部分都按字典序从小到大排列
- 这样就保证了新的字符串一定是大于当前字符串且最接近它的, 不可能有更小的了
- 下面的代码中有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N*N!)
- 最差情况下 N 个字符各不相同, 排列就有
N!
种, 从当前字符串转入下一个字符串最坏情况下需要O(N)
时间
- 最差情况下 N 个字符各不相同, 排列就有
- 空间复杂度
O(1)
- 只使用了几个变量 (不考虑输出结果集)
代码
class Solution: def permutation(self, s: str) -> List[str]: res = [] def getNext(s): for i in range(len(s) - 1)[::-1]: # 从后向前查找 if s[i] < s[i + 1]: # 找到目标字符了, 接下来找后面部分中大于s[i]且最接近它的字符 j = i + 1 while j < len(s) and s[j] > s[i]: j += 1 # s[j-1]就是后面部分中大于s[i]且最接近它的字符 j -= 1 # 单独拿出右边部分, 肯定严格按照降序排列 right = s[i + 1:j] + s[i] + s[j + 1:] # 交换字符后, 并加上右边的翻转部分(增序, 最小字典序), 就是下一个字典序的字符串 return s[0:i] + s[j] + right[::-1] # 没找到下一个字符串, 说明当前字符串就是字典序最大的了, 直接返回None return None # 先拿到字典序最小的字符串 s = ''.join(sorted(s)) while s is not None: res.append(s) s = getNext(s) return res
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107546322 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月29日 07时55分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
写论文,这个神器不能少!
2019-04-29
我在哥大读博的五年,万字总结
2019-04-29
本科、硕士、博士,究竟有何区别?
2019-04-29
如果我的实验室也这样布置,那多好。
2019-04-29
现在做硬件工程师还有前途吗?
2019-04-29
用 50 种编程语言写“Hello,World!”
2019-04-29
GD32替换STM32,这些细节一定要知道。
2019-04-29
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2019-04-29
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29