Python程式：查詢最長不共享字母的單詞

假設我們有一個包含小寫字母字串的列表，稱為words，我們需要找到兩個不同單詞長度之和的最大值，這兩個單詞不共享任何共同的字母。例如，如果輸入是words = ["abcd", "mno", "abdcmno", "amno"]，則輸出為7，因為不共享任何共同字母的單詞是["abcd", "mno"]，總長度為7。

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

  • 定義一個函式sign()。該函式將接收一個單詞作為輸入。
  • value := 0
  • 對於word中的每個字元c，執行：
    • value := value OR (2^(c的ASCII碼 - 'a'的ASCII碼))
  • 返回value
  • 在主方法中，執行以下操作：
  • signature := 一個列表，其中包含words中每個單詞x的sign(x)值。
  • ans := 0
  • 對於範圍從0到words大小的每個i，執行：
    • 對於範圍從i+1到words大小的每個j，執行：
      • 如果signature[i] AND signature[j] 等於 0，則
        • ans := ans和words[i]的大小 + words[j]的大小的最大值
  • 返回ans

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

class Solution:
   def sign(self, word):
      value = 0
      for c in word:
         value = value | (1 << (ord(c) - 97))
      return value
   def solve(self, words):
      signature = [self.sign(x) for x in words]
      ans = 0
      for i in range(len(words)):
         for j in range(i + 1, len(words)):
            if signature[i] & signature[j] == 0:
               ans = max(ans, len(words[i]) + len(words[j]))
      return ans
ob = Solution()
words = ["abcd", "mno", "abdcmno", "amno"]
print(ob.solve(words))

輸入

["abcd", "mno", "abdcmno", "amno"]

輸出

7

更新於：2020年10月19日

177 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告