LeetCode 472. Concatenated Words

Problem Statement
(Source) Given a list of words, please write a program that returns all concatenated words 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: ["catsdogcats","dogcatsdog","ratcatdogcat"]

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".

Note:

The number of elements of the given array will not exceed 10,000

The length sum of elements in the given array will not exceed 600,000 .

The returned elements order does not matter.

Solution

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        st = set(words)

        def helper(word):
            sta = [0]
            explored = {0}
            n = len(word)
            while sta:
                left = sta.pop()
                if left == n: return True
                for right in xrange(left+1, n+1):
                    if word[left : right] in st and right not in explored and (right != n or left > 0):
                        sta.append(right)
                        explored.add(right)
            return False

        return [word for word in words if word and helper(word)]