我有幾個單詞（字符串）像'hefg','dhck','dkhc','lmno'通過交換一些或所有字符來轉換為新單詞，這樣新單詞在字典上大于原始單詞，并且新單詞是所有單詞中最小的單詞大于原始單詞單詞。例如'dhck' 應該輸出'dhkc'而不是'kdhc'，'dchk'或任何其他。我有這些輸入hefgdhckdkhcfedcbabcd哪個應該輸出hegfdhkchcdkfedcbabdc我已經嘗試過在 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))
3 回答
慕勒3428872
TA貢獻1848條經驗 獲得超6個贊
你可以嘗試這樣的事情：
以相反的順序迭代字符串中的字符
跟蹤你已經看過的角色，以及你在哪里看到他們
如果您看到比當前字符大的字符，請將其與最小的較大字符交換
對該位置之后的所有字符進行排序以獲得最小字符串
示例代碼：
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
千萬里不及你
TA貢獻1784條經驗 獲得超9個贊
在一般情況下，最大字符及其位置不會影響算法。例如，對于'fedcbabcd'，您可以在字符串的開頭添加ana或 az并且不會改變您需要交換最后兩個字母的事實。
考慮輸入'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'。
慕碼人8056858
TA貢獻1803條經驗 獲得超6個贊
我們可以將您的問題改寫為查找 string 的下一個字典排列。
上述鏈接中的算法描述如下：
1) 找出最長的非遞增后綴
2）后綴左邊的數字是我們的支點
3）在后綴中找到pivot最右邊的后繼
4）交換后繼者和樞軸
5）反轉后綴
上面的算法特別有趣，因為它是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
添加回答
舉報
0/150
提交
取消