查找大于原始字符串的字符串的字符串操作算法

Question

我有几个单词（字符串）像'hefg','dhck','dkhc','lmno'通过交换一些或所有字符来转换为新单词，这样新单词在字典上大于原始单词，并且新单词是所有单词中最小的单词大于原始单词单词。例如'dhck' 应该输出'dhkc'而不是'kdhc'，'dchk'或任何其他。

我有这些输入

hefg

dhck

dkhc

fedcbabcd

哪个应该输出

hegf

dhkc

hcdk

fedcbabdc

我已经尝试过在 python 中使用这段代码，它适用于除'dkhc'和之外的所有内容'fedcbabcd'。我发现第一个字符'fedcbabcd'是最大值，所以它没有被交换。我得到"ValueError: min() arg is an empty sequence"

如何修改算法来解决这些问题？

list1=['d','k','h','c']

list2=[]

maxVal=list1.index(max(list1))

for i in range(maxVal):

    temp=list1[maxVal]

    list1[maxVal]=list1[i-1]

    list1[i-1]=temp

    list2.append(''.join(list1))

print(min(list2))

Answer 1

你可以尝试这样的事情：以相反的顺序迭代字符串中的字符跟踪你已经看过的角色，以及你在哪里看到他们如果您看到比当前字符大的字符，请将其与最小的较大字符交换对该位置之后的所有字符进行排序以获得最小字符串示例代码：def next_word(word):    word = list(word)    seen = {}    for i in range(len(word)-1, -1, -1):        if any(x > word[i] for x in seen):            x = min(x for x in seen if x > word[i])            word[i], word[seen[x]] = word[seen[x]], word[i]            return ''.join(word[:i+1] + sorted(word[i+1:]))        if word[i] not in seen:            seen[word[i]] = ifor word in ["hefg", "dhck", "dkhc", "fedcbabcd"]:    print(word, next_word(word))结果：hefg hegfdhck dhkcdkhc hcdkfedcbabcd fedcbabdc

Answer 2

在一般情况下，最大字符及其位置不会影响算法。例如，对于'fedcbabcd'，您可以在字符串的开头添加ana或 az并且不会改变您需要交换最后两个字母的事实。考虑输入'dgfecba'。在这里，输出是'eabcdfg'。为什么？请注意，最后六个字母按降序排列，因此通过更改其中的任何内容，您会得到一个按字典顺序排列的较小字符串，这是不好的。因此，您需要替换初始'd'.&nbsp;我们应该把什么放在它的位置？我们想要大于'd'，但尽可能小，所以'e'。剩下的六个字母呢？同样，我们希望有一个字符串，它是尽可能的小，所以我们排序的字母字典序：'eabcdfg'。所以算法是：从字符串的后面开始（右端）；在符号不断增加的同时向左走；让i成为最右边的位置s[i] < s[i + 1]；在我们的例子中，那是i= 0;保持位置 0, 1, ...,&nbsp;i- 1上的符号不变；找到i+1 ... n-1包含大于 的最少符号的位置s[i]；调用这个位置j；在我们的例子中，j= 3;交换s[i]和s[j];&nbsp;在我们的例子中，我们得到'egfdcba'；反转字符串s[i+1] ... s[n-1]；在我们的例子中，我们得到'eabcdfg'。

Answer 3

我们可以将您的问题改写为查找 string 的下一个字典排列。上述链接中的算法描述如下：1) 找出最长的非递增后缀2）后缀左边的数字是我们的支点3）在后缀中找到pivot最右边的后继4）交换后继者和枢轴5）反转后缀上面的算法特别有趣，因为它是O(n)。代码def next_lexicographical(word):&nbsp; &nbsp; word = list(word)&nbsp; &nbsp; # Find the pivot and the successor&nbsp; &nbsp; pivot = next(i for i in range(len(word) - 2, -1, -1) if word[i] < word[i+1])&nbsp; &nbsp; successor = next(i for i in range(len(word) - 1, pivot, -1) if word[i] > word[pivot])&nbsp; &nbsp; # Swap the pivot and the successor&nbsp; &nbsp; word[pivot], word[successor] = word[successor], word[pivot]&nbsp; &nbsp; # Reverse the suffix&nbsp; &nbsp; word[pivot+1:] = word[-1:pivot:-1]&nbsp; &nbsp; # Reform the word and return it&nbsp; &nbsp; return ''.join(word)StopIteration如果单词已经是最后一个词典排列，则上述算法将引发异常。例子words = [&nbsp; &nbsp; 'hefg',&nbsp; &nbsp; 'dhck',&nbsp; &nbsp; 'dkhc',&nbsp; &nbsp; 'fedcbabcd']for word in words:&nbsp; &nbsp; print(next_lexicographical(word))输出hegfdhkchcdkfedcbabdc