LeetCode如何输入字符串的排列

这篇文章主要介绍了LeetCode如何输入字符串的排列，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

我们提供的服务有：成都做网站、成都网站建设、微信公众号开发、网站优化、网站认证、太平ssl等。为近1000家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的太平网站制作公司

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

1 <= s 的长度 <= 8

题目样例

示例

输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

题目思考

1. 如何不重复地得到所有排列?

解决方案

思路

• 要想不重复地得到所有排列, 我们可以定义一个方法, 来求字典序的下一个排列, 正如题目示例中的输出数组的顺序那样
• 初始化为最小的字典序, 然后当遍历到最大的字典序的时候, 就说明所有排列都被找到了
• 所以算法的核心就是如何通过一个字符串找它的字典序的下一个排列
• 下一个排列一定是所有排列中大于当前字符串且最接近它的, 所以我们可以利用贪心算法, 具体步骤如下:
1. 从后向前找第一个                 小于后一个字符的字符 i (因为如果大于等于后一个字符的话, 就没法与后面的字符交换来使得整体字符串更大了)
2. 找刚才遍历的部分的大于且最接近 i 的字符 j
3. 将它们两个互换
4. 然后 i 往后的部分都按字典序从小到大排列
• 这样就保证了新的字符串一定是大于当前字符串且最接近它的, 不可能有更小的了
• 下面的代码中有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N*N!)
• 最差情况下 N 个字符各不相同, 排列就有                 N! 种, 从当前字符串转入下一个字符串最坏情况下需要                 O(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

感谢你能够认真阅读完这篇文章，希望小编分享的“LeetCode如何输入字符串的排列”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!