โปรแกรมหาความยาวสูงสุดของสองคำที่ไม่มีตัวอักษรร่วมกันใน Python

สมมติว่าเรามีรายการสตริงตัวพิมพ์เล็ก words หาผลรวมความยาวสูงสุดของสองคำที่ต่างกันและไม่มีตัวอักษรร่วมกัน

ตัวอย่าง: words = ["abcd", "mno", "abdcmno", "amno"] ผลลัพธ์ 7 (คำ "abcd" และ "mno" ไม่มีตัวอักษรซ้ำ รวมความยาว 4+3=7)

ขั้นตอนการแก้ปัญหา (Bitmask)

1. ฟังก์ชัน sign(word):
   • value = 0
   • สำหรับแต่ละ c ใน word: value |= (1 << (ord(c) - 97))
   • คืนค่า value (bitmask แสดงตัวอักษรที่มี)
2. signature = [sign(x) for x in words]
3. ans = 0
4. วนลูป i จาก 0 ถึง len(words)-1:
   • วนลูป j จาก i+1 ถึง len(words)-1:
     • ถ้า signature[i] & signature[j] == 0 (ไม่มีบิตร่วม):
       • ans = max(ans, len(words[i]) + len(words[j]))
5. คืนค่า ans

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

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

Output: 7