資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：檢測輸入單詞中是否存在短路
假設我們有一列單詞。我們必須檢查給定的單詞是否可以連線成一個環。只有當單詞A的最後一個字元與單詞B的第一個字元相同，單詞A才能放在單詞B的前面。每個單詞都必須使用，並且只能使用一次（首尾單詞不算）。
因此，如果輸入類似於words = ["ant","dog","tamarind","nausea","gun"]，則輸出為True。
為了解決這個問題，我們將遵循以下步驟：
graph := 一個新的鍵值對列表
seen := 一個新的集合
inDegree := 一個新的鍵值對列表
outDegree := 一個新的鍵值對列表
對於words中的每個單詞，執行：
start := word[0]
end := word[-1]
將end插入graph[start]的末尾
outDegree[start] := outDegree[start] + 1
inDegree[end] := inDegree[end] + 1
對於outDegree中的每個節點，執行：
如果outDegree[node]與inDegree[node]不同，則
返回False
dfs(words[0,0])
如果seen的大小與graph的大小相同，則返回seen的大小
定義一個函式dfs()。這將接受一個節點。
將node新增到seen中
對於graph[node]中的每個子節點，執行：
如果seen中不存在子節點，則
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
更新於：2020年12月23日
84 次瀏覽
廣告