Chương trình tìm tổng độ dài lớn nhất của hai từ không chia sẻ ký tự chung bằng Python

Cho danh sách các từ chữ thường words. Tìm tổng độ dài lớn nhất của hai từ khác nhau không chia sẻ ký tự chung.

Ví dụ: ["abcd", "mno", "abdcmno", "amno"] → 7 ("abcd" và "mno" không chia sẻ ký tự, tổng độ dài 4+3=7).

Quy trình giải quyết (Bitmask)

1. Đối với mỗi từ, tính "chữ ký" bitmask: bit i = 1 nếu từ chứa ký tự 'a' + i.
2. Với mỗi cặp từ (i, j), nếu signature[i] & signature[j] == 0 (không bit chung), cập nhật đáp án với tổng độ dài.
3. Trả về đáp án lớn nhất.

Ví dụ mã nguồn

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))  # Output: 7

Đầu vào

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

Đầu ra

7