求分析两种word break的写法

一种写的比较多，动态规划改记忆化递归写法：

1. class Solution(object):
   
2.     def wordBreak(self, s, wordDict):
   
3.         """
   
4.         :type s: str
   
5.         :type wordDict: List[str]
   
6.         :rtype: bool
   
7.         """
   
8.         ref={}
   
9.         
   
10.         def dfs(i):
    
11.             if i==0: ref[0]=True
    
12.             if i in ref: return ref[i]
    
13.             ref[i]=False
    
14.             for j in range(i):
    
15.                 if s[j:i] in wordDict and dfs(j):
    
16.                     ref[i]=True                 
    
17.             return ref[i]
    
18.             
    
19.         return dfs(len(s))

复制代码

另一种记忆化递归：

1. class Solution:
   
2.     def __init__(self):
   
3.         self.cache=collections.defaultdict()
   
4.         self.cache[""]=True
   
5.         
   
6.     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
   
7.         if s in self.cache: return self.cache[s]
   
8.       
   
9.         for i in range(len(s)):
   
10.             if s[:i+1] in wordDict:
    
11.                 if self.wordBreak(s[i+1:], wordDict):
    
12.                     self.cache[s]=True
    
13.                     return True
    
14.         self.cache[s]=False
    
15.         return False
    
16.    

复制代码

求分析两种写法的优缺点。复杂度感觉应该是一样的n^2。个人比较容易理解第二种写法。

谢谢。