class Solution(object):
    # Hack to remove an element from a list and make a copy.
    # There's probably a way better way to do this.
    def removeAndReturnList(self, words, toRemove):
        wordsCopy = words[:]
        wordsCopy.remove(toRemove)
        return wordsCopy

    # Dynamic programming solution based on the recursive solution
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """

        # Lengths of all words
        wordLen = len(words[0])

        # The last [wordLen] of these are the base case
        # In all other cases, we need this anyway so initialize it now
        # We could sort this first to bring this from O(mn^2) to O(mnlogn)
        wordLists = [[words] for i in range(len(s) + 1)]

        for i in range(len(s), wordLen-1, -1):
            substr = s[i-wordLen : i]  # The wordLen substr starting i from the end
            for wordList in wordLists[i]:
                # Here's where the sorting would help
                if substr in wordList:
                    wordLists[i-wordLen].append(self.removeAndReturnList(wordList, substr))


        out = []
        # Characters where empty lists exist are the solution
        for i in range(len(wordLists)):
            for words in wordLists[i]:
                if not words:
                    out.append(i)

        return out