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)
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.