Skip to main content

139. Word Break

分析

Pasted image 20220503230541.png


题解

Input

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

超时

function wordBreak(s: string, wordDict: string[]): boolean {
let ans = false

const dfs = (start) => {
if (start === s.length) {
ans = true
}
for (const wordKey of wordDict) {
const match = s.startsWith(wordKey, start)
if (match) {
dfs(start + wordKey.length)
}
}
}

dfs(0)

return ans
};

加memo

function wordBreak(s: string, wordDict: string[]): boolean {
let ans = false
const memo = new Array(s.length)

const dfs = (start) => {
if (ans) {
return
}
if (start === s.length) {
ans = true
}
if (memo[start] === false) return false
for (const wordKey of wordDict) {
const match = s.startsWith(wordKey, start)
if (match) {
dfs(start + wordKey.length)
}
}
memo[start] = false
}

dfs(0)

return ans
};

除去全局 ans 的使用(减少全局变量原则)

function wordBreak(s: string, wordDict: string[]): boolean {
const memo = new Array(s.length)

const dfs = (start: number) => {
if (memo[start] === false) {
return false
}
if (start === s.length) {
return true
}
for (const wordKey of wordDict) {
const match = s.startsWith(wordKey, start)
if (match && dfs(start + wordKey.length)) {
return true
}
}
memo[start] = false
return false
}

return dfs(0)
}
};```