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

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

在一般情况下，最大字符及其位置对算法没有影响。例如，对于'fedcbabcd'，您可以在字符串的开头预先加上a或z，这样就不会改变您需要交换最后两个字母的事实。你知道吗

考虑输入'dgfecba'。这里，输出是'eabcdfg'。为什么？请注意，最后六个字母是按降序排序的，因此通过更改其中的任何内容，可以按字典顺序得到一个较小的字符串，这是不好的。因此，您需要替换初始的'd'。我们应该用什么来代替它？我们想要比'd'大的东西，但要尽可能小，所以'e'。剩下的六个字母呢？同样，我们需要一个尽可能小的字符串，所以我们按字典顺序对字母排序：'eabcdfg'。你知道吗

所以算法是：

• 从字符串的后面开始（右端）
• 当符号不断增加时向左走
• 设i为最右边的位置，其中s[i] < s[i + 1]；在我们的例子中，i=0
• 保持位置0，1，…，i-1上的符号不变
• 在i+1 ... n-1中找到包含大于s[i]的最小符号的位置；将此位置称为j；在本例中，j=3
• 交换s[i]和s[j]；在我们的例子中，我们得到'egfdcba'
• 反转字符串s[i+1] ... s[n-1]；在本例中，我们得到'eabcdfg'。你知道吗

Answer 2

你的问题可以改写成finding the next lexicographical permutation of a string。你知道吗

上述链路中的算法描述如下：

1) Find the longest non-increasing suffix

2) The number left of the suffix is our pivot

3) Find the right-most successor of the pivot in the suffix

4) Swap the successor and the pivot

5) Reverse the suffix

上述算法特别有趣，因为它是O（n）。你知道吗

代码

def next_lexicographical(word):
    word = list(word)

    # Find the pivot and the successor
    pivot = next(i for i in range(len(word) - 2, -1, -1) if word[i] < word[i+1])
    successor = next(i for i in range(len(word) - 1, pivot, -1) if word[i] > word[pivot])

    # Swap the pivot and the successor
    word[pivot], word[successor] = word[successor], word[pivot]

    # Reverse the suffix
    word[pivot+1:] = word[-1:pivot:-1]

    # Reform the word and return it
    return ''.join(word)

如果单词已经是最后一个词典排列，上述算法将引发StopIteration异常。你知道吗

示例

words = [
    'hefg',
    'dhck',
    'dkhc',
    'fedcbabcd'
]

for word in words:
    print(next_lexicographical(word))

输出

hegf
dhkc
hcdk
fedcbabdc

Answer 3

您可以尝试以下方法：

• 按相反顺序迭代字符串中的字符
• 跟踪你已经看到的人物，以及你在哪里看到他们
• 如果看到比当前字符大的字符，请将其与最小的较大字符交换
• 对该位置后面的所有字符进行排序，以获得最小字符串

示例代码：

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