class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
#running time: O(mn^2), n = len(s), m = len(wordDict)
"""
Let‘s say the average word length in wordDict is k, so it takes n/k times to reach end.
Each time, the helper function would be called and it's running time is O(m*n)
So the whole runinng time would be O( m*n*n/k), which is O(m*n^2)
"""
dic=collections.defaultdict(list)
def helper(s):
if not s: return [None]
if s in dic: return dic[s]
res =[]
for word in wordDict:
n = len(word)
if word == s[:n]:
for each in helper(s[n:]):
if each:res.append(word+" "+each)
else: res.append(word)
dic[s] = res
return res
return helper(s)
Python DFS solution O(mn*n) running time


I don't think that running time is correct.
Just consider one example: the dictionary is consisted of character 'a' with various lengths, i.e. ['a', 'aa', 'aaa', 'aaaa', ...], and the last one has m a's. It is clear that when the given string contains n a’s, the complexity of output possibilities is closed to O(m^n).
By the way, I believe that ‘counting the number of solutions’ can be done within O(n * m) time complexity with hash function, where n is the size of string and m is the size of dictionary.
