140 word break ii time complexity

正在复习
https://leetcode.com/problems/word-break-ii/
对于时间复杂度的分析有些疑问
1.
我自己的解法， dp, dp[i] store all possible sentences to form str[0,i-1]

1.     public List<String> wordBreak(String s, List<String> wordDict) {
   
2.         List<String> [] dp = new ArrayList[s.length() + 1];
   
3.         Set<String> dictSet = new HashSet<>(wordDict);
   
4.         List<String> res = new ArrayList<>();
   
5.         //dp[i] : all possbile sentences to form s[0,i-1];
   
6.         for (int i = 0; i < dp.length; i++) {
   
7.             dp[i] = new ArrayList<>();
   
8.         }
   
9.         dp[0].add("");
   
10.         
    
11.         for (int i = 1; i < dp.length; i++) {
    
12.             for (int start = 0; start < i; start++) {
    
13.                 //when index operation is meesy, conisder a 1-element or 2-element case to test
    
14.                 String substr = s.substring(start, i);
    
15.                 if (!dp[start].isEmpty() && wordDict.contains(substr)) {
    
16.                     for (String prefix : dp[start]) {
    
17.                         dp[i].add(prefix + " " + substr);
    
18.                     }
    
19.                 }
    
20.             }
    
21.         }
    
22.         
    
23.         for (String sentence : dp[dp.length - 1]) {
    
24.             if (sentence.length() >= 1)
    
25.                 res.add(sentence.substring(1));
    
26.         }
    
27.         
    
28.         return res;
    
29.     }

复制代码

自己能确定的是 first loop O(n) * substring cost O(n), but can't decide time cost of nested loop ( for (String prefix : dp[start])
各位大佬能帮着看下吗.
2. lc 上 最快解法

1. public List<String> wordBreak(String s, List<String> wordDict) {
   
2.   if (s.length() > 100) {
   
3.             return new ArrayList();
   
4.         }
   
5.         
   
6.   List<String> result = new ArrayList<String> ();
   
7.   wordBreakUtil(s, wordDict, result, new StringBuilder());
   
8.   return result;
   
9. }
   
10.    
    
11.     public void wordBreakUtil(String s, List<String> wordDict, List<String> result, StringBuilder subList) {
    
12.         // add " " between 2 words in subList
    
13.   if (subList.length() != 0) {
    
14.    subList.append(" ");
    
15.   }
    
16.   // iterate over all the words in wordDict
    
17.         for (String word: wordDict) {
    
18.    
    
19.    if (s.startsWith(word)) {
    
20.     StringBuilder sb = new StringBuilder(subList);
    
21.        // append current match in sb
    
22.     sb.append(word);
    
23.        // if this is last word to be matched
    
24.     if (s.equals(word)) {
    
25.      result.add(new String(sb));
    
26.     } else {
    
27.      wordBreakUtil(s.substring(word.length()), wordDict, result, sb);
    
28.     }
    
29.             }
    
30.   }
    
31. }

复制代码

这个解法是在loop against wordDict, can perfect solve a very tricky test case on lc(which cause many other solution TLE)
我不是很确定这个解法的时间复杂度，分析是， O (len(s) ^ len(wordDict)). 理由是for each recursion node in recursion tree, loops by wordDict, so each recursion has len(wordDict)  branches, and whole recursion tree has height   len(s)

请大佬们帮忙看看