Python 中查詢透過一次交換得到的最小的字典序字串的程式

假設我們有一個字串 s，我們需要找到透過最多交換兩個字元可以得到的字典序最小的字串。

因此，如果輸入為 "zyzx"，則輸出將為 "xyzz"

為了解決這個問題，我們將遵循以下步驟：

• temp := 一個大小為 s 的陣列，並用 0 填充
• m:= s 的大小 - 1
• 對於 i 在 s 的大小 -1 到 -1 的範圍內，遞減 1，執行以下操作：
  • 如果 s[i] < s[m]，則
    • m := i
  • temp[i] := m
  • 對於 i 在 0 到 s 的大小的範圍內，執行以下操作：
    • a := temp[i]
    • 如果 s[a] 與 s[i] 不相同，則
      • 返回 s 的子字串（從索引 0 到 i）連線 s[a] 連線 s 的子字串（從索引 i+1 到 a）連線 s[i] 連線 s 的子字串（從索引 a+1 到結尾）
• 返回 s

示例

 即時演示

class Solution:
   def solve(self, s):
      temp = [0]*len(s)
      m=len(s)-1
      for i in range(len(s)-1, -1, -1):
         if s[i]<s[m]: m=i
            temp[i] = m
      for i in range(len(s)):
         a = temp[i]
         if s[a] != s[i]:
            return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
      return s
ob = Solution()
print(ob.solve("zyzx"))

輸入

zyzx

輸出

xyzz

Arnab Chakraborty

更新於: 2020-10-06

3K+ 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習