在 Python 中查詢給定兩個字串之間的字典序字串

假設我們有兩個字串 S 和 T，我們需要檢查是否存在一個與 S 和 T 長度相同的字串，並且該字串在字典序上大於 S 且小於 T。如果不存在這樣的字串，則返回 -1。我們需要記住，S = S1S2… Sn 在字典序上小於 T = T1T2… Tn，當且僅當存在一個 i，使得 S1= T1，S2= T2，… Si – 1= Ti – 1，Si < Ti。

因此，如果輸入像 S = "bbb" 和 T = "ddd"，則輸出將是 "bbc"

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

  • n := 字串的大小
  • 對於 i 從 n - 1 到 0，遞減 1，執行：
    • 如果字串[i] 不等於 'z'，則：
      • k := 字串[i] 的 ASCII 碼
      • 字串[i] := 來自 ASCII 碼 (k + 1) 的字元
      • 連線字串字元並返回
    • 字串[i] := 'a'

示例

讓我們看看下面的實現來更好地理解：

 線上演示

def find_next(string):
   n = len(string)
   for i in range(n - 1, -1, -1):
      if string[i] != 'z':
         k = ord(string[i])
         string[i] = chr(k + 1)
         return ''.join(string)
      string[i] = 'a'
S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
   print(res)
else:
   print(-1)

輸入

"bbb", "ddd"

輸出

bbc

更新於: 2020-08-28

217 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告