Chương trình tìm hiểu xem có ngắn mạch trong các từ nhập liệu bằng Python hay không

Giả sử chúng ta có một danh sách các từ. Chúng ta phải kiểm tra các từ đã cho có thể được xâu chuỗi để tạo thành một vòng tròn. Một từ A có thể được đặt trước một từ B khác trong một vòng tròn được xâu chuỗi nếu chỉ có ký tự cuối cùng của A trùng với ký tự đầu tiên của B. Mỗi từ phải được sử dụng và chỉ được sử dụng một lần (từ đầu tiên / cuối cùng sẽ không được xem xét).

Vì vậy, nếu đầu vào giống như các từ =["kiến", "chó", "me", "buồn nôn", "súng"], thì đầu ra sẽ là Đúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• graph:=một danh sách cặp khóa-giá trị mới

• đã thấy:=một tập hợp mới

• inDegree:=một danh sách cặp khóa-giá trị mới

• outDegree:=một danh sách cặp khóa-giá trị mới

• đối với mỗi từ trong từ, hãy thực hiện

  • start:=word [0]

  • end:=word [-1]

  • chèn end vào cuối biểu đồ [start]

  • outDegree [start]:=outDegree [start] + 1

  • inDegree [end]:=inDegree [end] + 1

• cho mỗi nút trong outDegree, thực hiện

  • nếu outDegree [node] không giống với inDegree [node], thì

    • trả về Sai

• dfs (từ [0,0])

• trả về kích thước đã xem nếu nó giống với kích thước của biểu đồ

• Định nghĩa một hàm dfs (). Điều này sẽ sử dụng nút.

  • thêm (nút) được xem

  • đối với mỗi phần tử con trong biểu đồ [node], thực hiện

    • nếu đứa trẻ không có mặt trong nhìn thấy, thì

    • dfs (con)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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