โปรแกรมนับจำนวนคำที่เป็นการต่อคำอื่นในรายการใน Python

มีรายการคำ หาจำนวนคำที่เป็นการต่อของคำอื่นในรายการเดียวกัน (ซ้ำได้, ต่อได้หลายคำ)

เช่น words=["hello","world","helloworld","famous","worldfamous","programming"] ให้ 2 ("helloworld"="hello"+"world", "worldfamous"="world"+"famous")

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

• สร้าง Trie จาก words ทุกคำ
• DFS ตรวจสอบแต่ละคำ: ที่โหนดจบคำ (*) ลองเรียก DFS ต่อจากตำแหน่งถัดไป
• ถ้าจบคำและต่อได้ ≥1 คำ คืน True
• นับคำที่ True

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

class Solution:
    def solve(self, words):
        trie = {}
        for word in words:
            layer = trie
            for w in word:
                if w not in layer: layer[w] = {}
                layer = layer[w]
            layer["*"] = ()
        def dfs(word, num):
            layer = trie
            for i,w in enumerate(word):
                if "*" in layer:
                    if dfs(word[i:], num+1): return True
                if w not in layer: return False
                layer = layer[w]
            return "*" in layer and num >= 1
        count = 0
        for word in words:
            count += dfs(word, 0)
        return count

ob = Solution()
words = ["hello","world","helloworld","famous","worldfamous","programming"]
print(ob.solve(words))

อินพุต

["hello","world","helloworld","famous","worldfamous","programming"]

เอาต์พุต

2