Chương trình kiểm tra chuỗi từ có tạo thành vòng tròn trong Python

Cho danh sách từ. Kiểm tra có thể sắp thành vòng tròn: từ A trước từ B nếu ký tự cuối A = ký tự đầu B. Mọi từ dùng đúng 1 lần.

Ví dụ: ["ant","dog","tamarind","nausea","gun"] → True (ant→tamarind→dog→gun→nausea→ant).

Giải pháp

Kiểm tra điều kiện Eulerian cycle trên đồ thị có hướng:

• Đồ thị: đỉnh = chữ cái, cạnh = từ (first -> last)
• Điều kiện cần đủ: in-degree = out-degree cho mọi đỉnh, và đồ thị liên thông (từ đỉnh bất kỳ có cạnh)
• DFS từ từ đầu tiên kiểm tra liên thông

Ví dụ minh họa

import collections
class Solution:
    def solve(self, words):
        self.graph = collections.defaultdict(list)
        self.seen = set()
        inDegree = collections.Counter()
        outDegree = collections.Counter()
        for word in words:
            start = word[0]
            end = word[-1]
            self.graph[start].append(end)
            outDegree[start] += 1
            inDegree[end] += 1
        for node in outDegree:
            if outDegree[node] != inDegree[node]:
                return False
        self.dfs(words[0][0])
        return len(self.seen) == len(self.graph)
    def dfs(self, node):
        self.seen.add(node)
        for child in self.graph[node]:
            if child not in self.seen:
                self.dfs(child)

ob = Solution()
print(ob.solve(["ant","dog","tamarind","nausea","gun"]))

Đầu vào

["ant","dog","tamarind","nausea","gun"]

Đầu ra

True