โปรแกรมหาความยาวสตริงที่ต่อกันได้จากอักขระที่ไม่ซ้ำกันใน Python

สมมติว่าเรามีรายการสตริงชื่อ words เราต้องสร้างสตริงโดยการต่อย่อยลำดับ (subsequence) ของคำใน words โดยที่อักขระทุกตัวในสตริงที่ได้ต้องไม่ซ้ำกัน เป้าหมายคือหาความยาวสูงสุดของสตริงดังกล่าว

ตัวอย่าง

อินพุต: words = ["xyz", "xyw", "wab", "cde"]

เราสามารถเลือกคำ "xyz", "wab", "cde" มาต่อกันได้ เพราะอักขระทั้งหมดไม่ซ้ำกัน (x,y,z,w,a,b,c,d,e) ความยาวรวม = 9

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

ใช้การค้นหาแบบทุกรูปแบบ (backtracking) พร้อมการตรวจสอบความไม่ซ้ำของอักขระ:

1. กำหนดตัวแปร ans = 0 เก็บความยาวสูงสุด
2. สร้างฟังก์ชันช่วย is_all_unique(s) ตรวจสอบว่าสตริง s มีอักขระไม่ซ้ำกันทั้งหมด
3. สร้างฟังก์ชันเวียนเกิด recur(i, cur):
   • i = ดัชนีคำปัจจุบัน, cur = สตริงที่ต่อมาแล้ว
   • ถ้า i == len(words) อัปเดต ans = max(ans, len(cur)) และคืนค่า
   • เรียก recur(i+1, cur) (ไม่เลือกคำนี้)
   • ถ้า words[i] เองมีอักขระไม่ซ้ำ และ cur + words[i] ก็ยังไม่ซ้ำ ให้เรียก recur(i+1, cur + words[i]) (เลือกคำนี้)
4. เริ่มต้นด้วย recur(0, "") และคืนค่า ans

การนำไปใช้ใน Python

class Solution:
    def solve(self, words):
        ans = 0
        def is_all_unique(s):
            return len(set(s)) == len(s)
        def recur(i=0, cur=""):
            nonlocal ans
            if i == len(words):
                ans = max(ans, len(cur))
                return
            recur(i + 1, cur)
            if is_all_unique(words[i]) and is_all_unique(cur + words[i]):
                recur(i + 1, cur + words[i])
        recur()
        return ans

ob = Solution()
words = ["xyz", "xyw", "wab", "cde"]
print(ob.solve(words))

อินพุต

["xyz", "xyw", "wab", "cde"]

เอาต์พุต

9