โปรแกรมเช็คว่าคำศัพท์สามารถจัดเป็นวงกลมได้หรือไม่ใน Python

คำอธิบายโจทย์

ให้ list ของคำ ตรวจสอบว่าจัดเป็นวงกลมได้ไหม โดยคำ A วางหน้า B ได้ก็ต่อเมื่อตัวอักษรสุดท้ายของ A = ตัวอักษรแรกของ B ใช้ทุกคำครั้งเดียว

ตัวอย่าง

words = ["ant","dog","tamarind","nausea","gun"] → True (ant→tamarind→dog→gun→nausea→ant)

วิธีแก้ปัญหา

Eulerian Circuit ใน Directed Graph:

1. สร้างกราฟ: โหนด = ตัวอักษร, Edge = คำ (start→end)
2. เงื่อนไข Eulerian Circuit: in-degree = out-degree ทุกโหนด + กราฟเชื่อมต่อ (connected)
3. DFS จากโหนดแรก เช็คว่าเยี่ยมครบทุกโหนดที่มี edge

โค้ด Python

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"]))

อินพุต

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

เอาต์พุต

True