解決https://leetcode.com/problems/word-break/的一種方法是使用陣列進行記憶。
該解決方案聲稱它將具有 O(N) 的空間復雜度。
但是，我認為它應該更接近 O(N^2)，因為在每個遞回級別，我們都會進行 substring operation s[start:end]。這是準確的嗎？
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@lru_cache
def wordBreakMemo(s: str, word_dict: FrozenSet[str], start: int):
if start == len(s):
return True
for end in range(start 1, len(s) 1):
if s[start:end] in word_dict and wordBreakMemo(s, word_dict, end):
return True
return False
return wordBreakMemo(s, frozenset(wordDict), 0)
uj5u.com熱心網友回復：
但是，我認為它應該更接近 O(N^2)，因為在每個遞回級別，我們都會進行 substring operation
s[start:end]。這是準確的嗎？
在這種情況下不是。讓我們分解這一行中的操作：
if s[start:end] in word_dict and wordBreakMemo(s, word_dict, end):
- 取子串
s[start:end] - 檢查子字串是否在 word_dict 中。
- （短路）如果不是，則跳過 if 塊。
- 呼叫 wordBreakMemo，檢查回傳值。
- 如果為真，則進入 if 塊。
需要注意的是子字串沒有分配給變數，我們在第 2 步之后完成了它。在遞回之前，它在此時被釋放。因此，一次只能分配一個子字串：屬于堆疊頂部函式的子字串。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452505.html
上一篇：這個反向鏈接串列代碼有什么問題？
下一篇：接受字串并識別連續字母數的代碼