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

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]] = i

for word in ["hefg", "dhck", "dkhc", "fedcbabcd"]:
    print(word, next_word(word))

结果:

hefg hegf
dhck dhkc
dkhc hcdk
fedcbabcd fedcbabdc