LC-0472 Hard LeetCode

472. Concatenated Words

Array String Dynamic Programming Depth-First Search Trie

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 49% Topics: Array, String, Dynamic Programming, Depth-First Search, Trie

Reading material

Arrays & Hashing 12 min Strings 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n * l^2)
# Space: O(n * l)

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        lookup = set(words)
        result = []
        for word in words:
            dp = [False] * (len(word)+1)
            dp[0] = True
            for i in xrange(len(word)):
                if not dp[i]:
                    continue

                for j in xrange(i+1, len(word)+1):
                    if j - i < len(word) and word[i:j] in lookup:
                        dp[j] = True

                if dp[len(word)]:
                    result.append(word)
                    break

        return result

Solution from kamyu104/LeetCode-Solutions · MIT