Chương trình tìm độ dài tối đa của các từ không chia sẻ bằng Python

Giả sử chúng ta có một danh sách các chuỗi chữ cái viết thường được gọi là các từ, chúng ta phải tìm tổng độ dài lớn nhất của hai từ riêng biệt không có chung một chữ cái. Vì vậy, nếu đầu vào giống như words =["abcd", "mno "," Abdcmno "," amno "], thì đầu ra sẽ là 7, vì các từ không có chung chữ cái nào là [" abcd "," mno "], tổng độ dài là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một dấu chức năng (). Điều này sẽ có từ
• giá trị:=0
• đối với mỗi c trong word, hãy thực hiện
  • giá trị:=giá trị OR (2 ^ (ASCII của c - ASCII của 'a'))
• giá trị trả về
• Từ phương pháp chính, hãy thực hiện như sau
• chữ ký:=một danh sách có dấu (x) cho mỗi chữ x trong các từ
• ans:=0
• đối với tôi trong phạm vi từ 0 đến kích thước của từ, hãy thực hiện
  • đối với j trong phạm vi i + 1 theo kích thước của từ, hãy thực hiện
    • nếu chữ ký [i] VÀ chữ ký [j] giống 0, thì
      • ans:=tối đa ans và kích thước của từ [i] + kích thước của từ [j]
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

7