# Python DFS solution O(mn*n) running time

• ``````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)``````

• NIce solution, kudos

• Can you explain that runtime?

• Hi, I made a mistake in the running time. I corrected it and added some comments about the time complexity. Hope it's clear. :p

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

• @wrangle1005 Agreed. The DFS part definitely takes longer than mnn time.

• My solution is even faster than yours and the time by avoiding useless state calculation and time complexity I concluded is exponential. Thus, I don't think this is a P time algorithm even if it works well in most cases.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.