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

สมมติว่าเรามีรายการของสตริงตัวอักษรตัวพิมพ์เล็กที่เรียกว่าคำ เราต้องหาผลรวมสูงสุดของความยาวสองคำที่แตกต่างกันซึ่งไม่มีตัวอักษรร่วมกัน ดังนั้นหากการป้อนเป็นเหมือนคำ =["abcd", "mno ", "abdcmno", "amno"] จากนั้นผลลัพธ์จะเป็น 7 เนื่องจากคำที่ไม่มีตัวอักษรทั่วไปคือ ["abcd", "mno"] ความยาวรวมคือ 7

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน sign() นี้จะใช้เวลาคำพูด
• ค่า :=0
• สำหรับแต่ละ c ใน word ทำ
  • value :=value OR (2^(ASCII of c - ASCII of 'a'))
• คืนค่า
• จากวิธีหลัก ให้ทำดังนี้
• ลายเซ็น :=รายการที่มีเครื่องหมาย (x) สำหรับแต่ละ x ในคำ
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของคำ ให้ทำ
  • สำหรับ j ในช่วง i + 1 ถึงขนาดของคำ ให้ทำ
    • ถ้า signature[i] AND signature[j] เหมือนกับ 0 แล้ว
      • ans :=สูงสุดของ ans และขนาดของคำ[i] + ขนาดของคำ[j]
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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