단어 목록이 있다고 가정합니다. 우리는 주어진 단어가 연결되어 원을 형성할 수 있는지 확인해야 합니다. A의 마지막 문자가 B의 첫 번째 문자와 동일한 경우 A 단어는 연쇄 원에서 다른 단어 B 앞에 배치될 수 있습니다. 모든 단어는 사용해야 하며 한 번만 사용할 수 있습니다(첫 번째/마지막 단어 고려되지 않음).
따라서 입력이 단어 =["ant","dog","tamarind","nausea","gun"]과 같으면 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
그래프 :=새로운 키-값 쌍 목록
-
본 :=새로운 세트
-
inDegree :=새로운 키-값 쌍 목록
-
outDegree :=새로운 키-값 쌍 목록
-
단어의 각 단어에 대해 수행
-
시작 :=단어[0]
-
끝 :=단어[-1]
-
그래프 끝에 끝 삽입[start]
-
outDegree[시작] :=outDegree[시작] + 1
-
inDegree[end] :=inDegree[end] + 1
-
-
outDegree의 각 노드에 대해 수행
-
outDegree[노드]가 inDegree[노드]와 같지 않으면
-
거짓을 반환
-
-
-
dfs(단어[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