Compound words problem, Here's the code I have tried below, but this doesn't work, it won't return all the possible pairs, it only returns one pair of a word ex:
"verylongjump": ["very", "long", "jump"])
but it will not return both:
"verylongjump": ["very", "long", "jump"]
"verylongjump": ["very","longjump"]
Question Input:
Input:
["long", "very", "jump", "verylongjump", "longjump",
"iconstar", "star", "icon", "icons", "tar", "stars,"iconstars"]
Expected Output:
"verylongjump": ["very", "long", "jump"]
"verylongjump": ["very","longjump"]
"iconstar": ["icon",""star"]
"iconstar":["icons", "tar"]
"iconstars":["icon","stars"]
def concatenatedWords(words):
# Intitialize empty array for result set
result = []
# Helper function for Work Break II without DP but accepted by LeetCode
def helper(idx, word, wordSet, curr, result):
if idx == len(word):
result.append(curr)
return
if idx > len(word):
return
for i in range(idx+1, len(word)+1):
if word[idx:i] in wordSet:
helper(i, word, wordSet, curr + [word[idx:I]], result)
return
# Convert the list of words into a HashSet
wordSet = set(words)
# Find word breaks for each word
for word in words:
# Initialize current word split result set
curr = []
helper(0, word, wordSet, [], curr)
# Word Break solution captures the word themselves as they are present in the
# hash set; Filter them out by checking for length of current splits more than 1
if len(curr) > 1:
res = []
# Flatten the result list
for elem in curr:
res.extend(elem)
result.append(res)
return result