Chương trình đếm số từ là nối của các từ khác trong danh sách bằng Python

Cho danh sách words. Đếm số từ là nối (concatenation) của một hoặc nhiều từ khác cũng trong danh sách (có thể dùng lại từ).

Ví dụ: ["hello","world","helloworld","famous","worldfamous","programming"] → 2 ("helloworld", "worldfamous").

Giải thuật

• Xây Trie từ danh sách từ, đánh dấu cuối từ bằng khóa "*".
• Hàm dfs(word, num_concatenated): duyệt Trie theo word, khi gặp "*" thử đệ quy phần còn lại với num_concatenated+1.
• Nếu đến cuối từ và num_concatenated >= 1 → True.
• Đếm số từ trong danh sách thỏa mãn dfs(word, 0).

Ví dụ minh họa

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_concatenated_words):
            layer = trie
            for i, w in enumerate(word):
                if "*" in layer:
                    if dfs(word[i:], num_concatenated_words + 1):
                        return True
                if w not in layer:
                    return False
                layer = layer[w]
            if "*" in layer and num_concatenated_words >= 1:
                return True
            return False
        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))

Đầu vào

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

Đầu ra

2