CODEWITHSUNDEEP
pythonpython-3.xrecursiondynamic-programming
coderWorld
coderWorld

Reputation: 642

Find list of words used for concatenating?

Given a list of words (without duplicates), please write a program that returns all words used for concatenating in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example: Input: ["cat","cats","catsdogcats","dog", "dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["cats","dog","cats", "rat"]

Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

I have the solution for returning the concatenated words for example in this case should be: ["catsdogcats","dogcatsdog","ratcatdogcat"]

'''
If a word can be Concatenated from shorter words, then word[:i] and word[i:] must also be Concatenated from shorter words.
Build results of word from results of word[:i] and word[i:]
Iterate i from range(1, len(word)) to avoid a word is Concatenated from itself.
Use memorization to avoid repeat calculation.
Time: O(n*l)
Space: O(n)
'''
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        mem = {}
        words_set = set(words)
        return [w for w in words if self.check(w, words_set, mem)]

    def check(self, word, word_set, mem):
        if word in mem:
            return mem[word]
        mem[word] = False
        for i in range(1, len(word)):
            if word[:i] in word_set and (word[i:] in word_set or self.check(word[i:], word_set, mem)):
                mem[word] = True
                break
        return mem[word]

How do I return the words used for concatenation instead?

Upvotes: 0

Views: 649

Answers (2)

Red
Red

Reputation: 27567

First, we sort the list by the length of each string, so the pend_words function can find the largest word that is in the word it is checking.

For example: the string 'catscats' contains both 'cat' and 'cats', but if it chose 'cat' as part of 'catscats', our program will never find out 'cats'. If 'cats' is not in our string, the program will gradually find 'cat' as it goes through the list of sorted strings.

The function pend_words retrieves words in the list that contain other words, and remove that part of the word.

The function confirm_words checks the pending list. For every string in the list that is empty, that means that the string is made completely out of other words, so it will add that word to the justified list.

l = ['cats','cat','dogcats','dog','catpig','pigs','pigspigs','goatdog','goat','rabbit']


def pend_words():
    global word,modified
    for _ in range(len(word)):
        for wor in l:
            if wor in word and not(wor == word and modified==False):
                word = word.replace(wor,'',1)
                modified = True
                pending.append(wor)

def confirm_words():
    global word
    if word == '':
        for wo in pending:
            if wo not in justfied:
                justfied.append(wo)

l.sort(key=len,reverse=True)
justfied = []

for word in l:

    pending = [] # Create an empty list to pend each potential word (potential because it contains another word)
    modified = False # Before we pend the word, the word hasn't been modified
    pend_words()
    confirm_words()
print(justfied)

Upvotes: 0

Red
Red

Reputation: 27567

I found the solution:

Input:

l = ['cats','cat','dogcats','dog','catpig','pigs','pigspigs','goatdog','goat','rabbit']

l.sort(key=len,reverse=True) # Sort the list from most letters to least
justfied = [] # List of justified strings
for word in l:
    pending = [] # List of pending strings
    modified = False # Check whether a string have been modified
    for _ in range(len(word)):
        for wor in l:
            if wor in word and not(wor == word and modified==False):
                word = word.replace(wor,'',1)
                modified = True
                pending.append(wor)
    if word == '':
        for wo in pending:
            if wo not in justfied:
                justfied.append(wo)
print(justfied)

Output:

['pigs', 'cats', 'dog', 'goat']

Upvotes: 1

Related Questions