permsubwords.py

# list[t] -> list[list[t]]
def perm(xs):
    if len(xs) < 2:
        yield xs
    else:
        for i in range(len(xs)):
            head, tail = xs[i], xs[:i] + xs[i+1:]
            for p in perm(tail):
                yield [head]+p


# str -> list[str] -> list[int]
def findSubstring(s, words):
    result = []
    for i, c in enumerate(s):
        for j, p in enumerate(perm(words)):
            word = str.join('', p)
            if subword(word, s[i:]):
                result.append(i)
    return result


# str -> str -> bool
def subword(word, s):
    for i, c in enumerate(word):
        if s[i] != c:
            return False
    return True


# result: [0,9]
print(findSubstring('barfoothefoobarman', ['foo', 'bar']) == [0, 9])