Time Complexity and Space Complexity of the Python Code

Can someone please help me with the time and space complexity of this code snippet? Please refer to the leetcode question- Word break ii.Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

def wordBreak(self, s, wordDict):
    dp = {}
    def word_break(s):
        if s in dp:
            return dp[s]
        result = []
        for w in wordDict:
            if s[:len(w)] == w:
                if len(w) == len(s):
                    result.append(w)
                else:
                    tmp = word_break(s[len(w):])
                    for t in tmp:
                        result.append(w + " " + t)
        dp[s] = result
        return result
    
    return word_break(s)

Decision Tree

Time Complexity

• height of tree is len(target)=m in worst case
• branching is len(words)=n
• in each recursive call, you make slicing if s[:len(w)]. worst case is m
• T: O(N^m * M)=O(n^m)

Space complexity

• space from call stack is the height of tree=m
• IN each recursive call you are making suffix and storing it. its length is m
• S : O(m*m)