139.单词拆分.md

139.单词拆分

/*
 * @lc app=leetcode.cn id=139 lang=typescript
 *
 * [139] 单词拆分
 */

// @lc code=start
function wordBreak(s: string, wordDict: string[]): boolean {}
// @lc code=end

解法 1: 暴力枚举

function wordBreak(s: string, wordDict: string[]): boolean {
  const cache = new Set<string>()
  const helper = (i: number, wordDictMap: Array<{ word: string; index: number }>): boolean => {
    if (!wordDictMap.length) return false

    if (i === s.length) return false

    let tmp = []

    for (const { word, index } of wordDictMap) {
      if (word[index] === s[i]) {
        if (index === word.length - 1) {
          if (i === s.length - 1) return true

          wordDict
          tmp.push(...wordDict.map(word => ({ word, index: 0 })))
        } else {
          tmp.push({ word, index: index + 1 })
        }
      }
    }
    return helper(i + 1, tmp)
  }
  return helper(
    0,
    wordDict.map(word => ({ word, index: 0 })),
  )
}

加缓存

使用 map 来过滤掉重复数据

function wordBreak(s: string, wordDict: string[]): boolean {
  const helper = (i: number, wordDictMap: Map<string, { word: string; index: number }>): boolean => {
    if (!wordDictMap.size) return false

    if (i === s.length) return false

    let tmp = new Map()

    for (const [, { word, index }] of wordDictMap) {
      if (word[index] === s[i]) {
        if (index === word.length - 1) {
          if (i === s.length - 1) return true

          wordDict.forEach(word => tmp.set(`${word}0`, { word, index: 0 }))
        } else {
          tmp.set(`${word}${index + 1}`, { word, index: index + 1 })
        }
      }
    }
    return helper(i + 1, tmp)
  }
  return helper(
    0,
    new Map<string, { word: string; index: number }>(wordDict.map(word => [`${word}0`, { word, index: 0 }])),
  )
}

递归

function wordBreak(s: string, wordDict: string[]): boolean {
  let dp = [new Map<string, [string, number]>(wordDict.map(word => [`${word}0`, [word, 0]]))]
  for (let i = 1; i <= s.length; i++) {
    if (dp[i - 1].size === 0) return false

    dp[i] = new Map()
    for (const [, [word, index]] of dp[i - 1]) {
      if (s[i - 1] === word[index]) {
        if (index === word.length - 1) {
          if (i === s.length) return true
          wordDict.forEach(word => dp[i].set(`${word}0`, [word, 0]))
        } else {
          dp[i].set(`${word}${index + 1}`, [word, index + 1])
        }
      }
    }
  }
  return false
}

解法 2: 动态规划

• 状态: 以第 i 个字符结尾时,能否被单词表拆分
• 递推公式: dp[j-1] && words.has(s[j~i]) && dp[i]=true
• 边界: dp[0]=true

function wordBreak(s: string, wordDict: string[]): boolean {
  let [max, min, words] = [-Infinity, Infinity, new Set<string>()]
  for (const word of wordDict) {
    words.add(word)
    const len = word.length
    ;[max, min] = [Math.max(max, len - 1), Math.min(min, len - 1)]
  }

  const dp = [true, ...new Array(s.length).fill(false)]
  for (let i = min; i < s.length; i++) {
    for (let j = Math.max(i - max, 0); j <= i - min; j++) {
      if (dp[j] && words.has(s.slice(j, i + 1))) dp[i + 1] = true
    }
  }
  return dp[dp.length - 1]
}

Case

test.each([
  { input: { s: 'leetcode', wordDict: ['leet', 'code'] }, output: true },
  { input: { s: 'applepenapple', wordDict: ['apple', 'pen'] }, output: true },
  {
    input: { s: 'catsandog', wordDict: ['cats', 'dog', 'sand', 'and', 'cat'] },
    output: false,
  },
  {
    input: { s: 'a', wordDict: ['b'] },
    output: false,
  },
  { input: { s: 'aaaaaaa', wordDict: ['aaaa', 'aa'] }, output: false },
])('input: s = $input.s, wordDict = $input.wordDict', ({ input: { s, wordDict }, output }) => {
  expect(wordBreak(s, wordDict)).toEqual(output)
})