Python DFS solution O(mn*n) running time


  • 3
    S
    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)

  • 0

    NIce solution, kudos


  • 0

    Can you explain that runtime?


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


  • 1
    W

    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.


  • 0
    G

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


  • 0

    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.


Log in to reply
 

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