Repository navigation
Expand file tree
/
Copy path472_Concatenated_Words.py
More file actions
97 lines (75 loc) · 2.56 KB
/
Copy path472_Concatenated_Words.py
File metadata and controls
97 lines (75 loc) · 2.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# # Using Trie and DFS
# from collections import defaultdict
# class TrieNode:
# def __init__(self):
# self.children = defaultdict(TrieNode)
# self.isWord = False
# self.finalWord = None
# class Trie:
# def __init__(self):
# self.root = TrieNode()
# def addWord(self, word):
# currentNode = self.root
# for char in word:
# if char not in currentNode.children:
# currentNode.children[char] = TrieNode()
# currentNode = currentNode.children[char]
# currentNode.isWord = True
# currentNode.finalWord = word
# class Solution(object):
# def findAllConcatenatedWordsInADict(self, words):
# """
# :type words: List[str]
# :rtype: List[str]
# """
# if not words or len(words) <= 0:
# return []
# trie = Trie()
# for word in words:
# trie.addWord(word)
# result = []
# for word in words:
# if self.isConcatenated(trie.root, word, 0, 0):
# result.append(word)
# return result
# # DFS method to check word concatination
# # Return true if word starting from index is concatenated
# def isConcatenated(self, trieRoot, word, startIdx, concatWordCnt):
# if startIdx == len(word):
# return concatWordCnt >= 2
# for i in range(startIdx, len(word)):
# char = word[i]
# if char not in trieRoot.children:
# return False
# trieRoot = trieRoot.children[char]
# if trieRoot.isWord:
# # if trieRoot.finalWord != word:
# if self.isConcatenated(trieRoot, word, i + 1, concatWordCnt + 1):
# return True
# # else:
# # return concatWordCnt > 1
# return False
# Using only DFS
class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
d = set(words)
def dfs(word):
for i in range(1, len(word)):
prefix = word[:i]
suffix = word[i:]
if prefix in d and suffix in d:
return True
if prefix in d and dfs(suffix):
return True
if suffix in d and dfs(prefix):
return True
return False
res = []
for word in words:
if dfs(word):
res.append(word)
return res