按字典序打印字符串的所有排列
1. 我只能找到一个字符串的所有排列,然后进行排序吗?这将仅具有时间复杂度O(n!) ->对于查找排列,然后对其进行排序,它是
2. geeksforgeeks提供的解决方案称其为
请问哪种方法最好并且时间复杂度是多少?请解释。
1. 我只能找到一个字符串的所有排列,然后进行排序吗?这将仅具有时间复杂度O(n!) ->对于查找排列,然后对其进行排序,它是
O(nlogn)
(如果快速排序或合并被视为排序算法)。 O(n!)+O(nlogn)
将是复杂度。2. geeksforgeeks提供的解决方案称其为
O(n*n!)
。请参考链接:http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
3. 我在https://www.educative.io/page/11000001/90001上找到了另一种解决方案。请问哪种方法最好并且时间复杂度是多少?请解释。
O(n!)
,除非你可以以某种方式修改排列生成算法,在不进行额外工作的情况下拒绝非排序字符串。 - Tim Biegeleisen