สมมติว่าเรามีรายการคำ เราต้องตรวจสอบคำที่ให้มาว่าสามารถโยงเป็นวงกลมได้ คำ A สามารถวางหน้าคำอื่น B ในวงกลมที่มีลูกโซ่ได้ ถ้าเฉพาะอักขระตัวสุดท้ายของ A เท่านั้นที่เหมือนกันกับอักขระตัวแรกของ B ทุกคำต้องใช้และใช้ได้เพียงครั้งเดียว (คำแรก/คำสุดท้าย จะไม่รับพิจารณา)
ดังนั้น หากอินพุตเป็นเหมือนคำ =["ant","dog","tamarind","nausea","gun"] ผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กราฟ :=รายการคู่คีย์-ค่าใหม่
-
เห็นแล้ว :=ชุดใหม่
-
inDegree :=รายการคู่คีย์-ค่าใหม่
-
outDegree :=รายการคู่คีย์-ค่าใหม่
-
สำหรับแต่ละคำในคำ ทำ
-
start :=word[0]
-
จบ :=word[-1]
-
แทรกจุดสิ้นสุดที่จุดสิ้นสุดของกราฟ[เริ่มต้น]
-
outDegree[start] :=outDegree[start] + 1
-
inDegree[end] :=inDegree[end] + 1
-
-
สำหรับแต่ละโหนดใน outDegree ให้ทำ
-
ถ้า outDegree[node] ไม่เหมือนกับ inDegree[node] แล้ว
-
คืนค่าเท็จ
-
-
-
dfs(words[0,0])
-
ขนาดผลตอบแทนที่เห็นถ้าเท่ากับขนาดของกราฟ
-
กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด
-
เพิ่ม (โหนด) ที่เห็น
-
สำหรับเด็กแต่ละคนในกราฟ[โหนด] ทำ
-
ถ้าเด็กไม่อยู่ในที่เห็นแล้ว
-
dfs(ลูก)
-
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
