在这个问题中，我们将使用数组的字母数字字符查找所有 Lyndon 单词。
在开始之前，让我们先了解一下 Lyndon 一词的定义。
所有单词都是 Lyndon 单词，严格按照字典顺序小于其所有循环。
以下是 Lyndon 单词的示例。
立即学习“Python免费学习笔记（深入）”；
ab - “ab”严格按照字典顺序小于其所有排列“ba”。
89 - ‘89’的旋转是‘98’，严格按字典顺序大于‘89’。
abc - ‘abc’的旋转是‘bca’和‘cab’，它们严格大于‘abc’。
以下是非 Lyndon 单词的示例。
aaa - aaa 是非林登词，因为“aaa”的所有旋转都是相同的。
bca - ‘bca’是非林登词，因为‘abc’它的旋转比它小，
问题陈述- 我们给出了一个长度为 K 的字符数组，其中包含字母数字字符。此外，我们还给出了包含正整数的 n。任务是我们需要使用数组中给出的字母数字字符找到长度为 n 的所有 Lyndon 单词。
示例
输入
chars = ['1', '3', '2'], n = 3
输出
112, 113, 122, 123, 132, 133, 223, 233
解释- 它使用数组字符生成了长度为 3 的所有 Lydon 字。
输入
n = 2, chars = ['1', '0']
输出
01
解释-“01”是我们可以使用 0 和 1 组成的唯一 Lyndon 词。
输入
n = 2, chars = ['c', 'a', 'd']
输出
ac, ad, cd
解释- 它使用 a、c 和 d 字符生成长度为 2 的 Lyndon 单词。
远航CMS(yhcms)是一套基于PHP+MYSQL为核心开发的专业营销型企业建站系统。是国内首家免费+开源自带分站系统的php内容管理系统。长期以来不断的完善、创新，远航CMS会为您带来全新的体验！产品十大优势：模板分离：模板程序分离，深度二次开发三网合一：电脑/手机/微信 多终端访问自定义广告：图片/文字/动画定时发布：SEO维护，无需人工值守多词生成：栏目关键词多方案生成SEO设置：自定义U
方法 1
我们有一种特殊的算法来生成林登词，称为杜瓦尔算法。
算法
第 1 步- 定义代表 Lyndon 单词长度的“n”值和包含创建 Lyndon 单词时要使用的字符的 chars 数组。
第 2 步- 对列表进行排序。
步骤 3 − 用−1 初始化“索引”列表。
第 4 步- 进行迭代，直到索引列表不为空。
第 5 步- 将“索引”列表的最后一个元素增加 1。
第 6 步− 如果 list_size 等于 n，则打印列表值。
第 7 步- 将索引附加到列表，使其长度等于 n。
第 8 步- 如果列表的最后一个元素等于数组的最后一个索引，则将其从列表中删除。
示例
让我们通过示例输入来了解示例。
排序后的列表将为 ['a', 'c', 'd']。
索引列表将在第一次迭代中从 [−1] 更新到 [0]。之后索引的长度就等于2，变成[0, 0]。
在第二次迭代中，列表将更新为 [0, 1]，我们找到了第一个 Lyndon 单词“ac”。
在第三次迭代中列表将变为 [0, 2]，第二个 Lyndon 单词是“ad”。另外，从列表中删除最后一个元素，因为它等于 array_len -1。
在第四次迭代中，列表将变为 [1]。之后将更新 [1, 1]。
在下一次迭代中列表将变为 [1, 2]，并且我们找到了第三个 Lyndon wor，''cd'。
# Input
n = 2
chars = ['c', 'a', 'd']
# sort the list
initial_size = len(chars)
chars.sort()
# Initializing the list
indexes = [-1]
print("The Lyndon words of length {} is".format(n))
# Making iterations
while indexes:
# Add 1 to the last element of the list
indexes[-1] += 1
list_size = len(indexes)
# If the list contains n characters, it means we found a Lyndon word
if list_size == n:
print(''.join(chars[p] for p in indexes))
# Make the list size equal to n by adding characters
while len(indexes) < n:
indexes.append(indexes[-list_size])
while indexes and indexes[-1] == initial_size - 1:
indexes.pop()
输出
The Lyndon words of length 2 is ac ad cd
时间复杂度− O(nlogn)，因为我们需要首先对“字符”列表进行排序。
空间复杂度− O(n)，因为我们在列表中存储 n 个索引。
Duval 算法是生成长度为 n 的 Lyndon 词的最有效方法。但是，我们已经自定义了仅使用数组字符的方法。
