使用 Python 查詢最長 Nice 子字串的程式

假設我們有一個字串 s。我們必須找到 s 的最長 Nice 子字串。對於一個字串 s，當字母表中的每個字母在 s 中都以大寫和小寫兩種形式出現時，它就被認為是 Nice 的。如果有多個這樣的子字串，則返回最早出現的子字串。

因此，如果輸入類似於 s = "ZbybBbz"，則輸出將為 "bBb"，因為它包含小寫和大寫 B。

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

  • cur_max:= -1

  • res:= 空字串

  • 對於 i 從 0 到 s 的大小，執行以下操作

    • c := s[i]

    • upper := 一個新的集合

    • lower := 一個新的集合

    • 如果 c 是小寫，則

      • 將 c 新增到 lower 中

    • 如果 c 是大寫，則

      • 將 c 新增到 upper 中，但在之前將其轉換為小寫

    • 對於 j 從 i+1 到 s 的大小，執行以下操作

      • c := s[j]

      • 如果 c 是小寫，則

        • 將 c 新增到 lower 中

      • 如果 c 是大寫，則

        • 將 c 新增到 upper 中，但在之前將其轉換為小寫

      • 如果 upper 等於 lower，則

        • 如果 j-i > cur_max，則

          • cur_max := j-i

          • res := s 從索引 i 到 j+1 的子字串

  • 返回 res

讓我們看看以下實現以獲得更好的理解：

示例

 即時演示

def solve(s):
   cur_max= -1
   res=""
   for i in range(len(s)):
      c = s[i]
      upper = set()
      lower = set()
      if c.islower():
         lower.add(c)
      if c.isupper():
         upper.add(c.lower())
      for j in range(i+1,len(s)):
         c = s[j]
         if c.islower():
            lower.add(c)
         if c.isupper():
            upper.add(c.lower())
         if upper == lower:
            if j-i>cur_max:
               cur_max = j-i
               res = s[i:j+1]
   return res
s = "ZbybBbz"
print(solve(s))

輸入

"ZbybBbz"

輸出

bBb

更新於: 2021年5月29日

477 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.