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"]

输出

Arnab Chakraborty

更新于：2020年10月19日

177 次浏览

开启您的职业生涯

完成课程获得认证

开始学习