139.单词拆分

链接：139.单词拆分
难度：Medium
标签：字典树、记忆化搜索、数组、哈希表、字符串、动态规划
简介：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

题解 1 - typescript

• 编辑时间：2020-06-25
• 执行用时：96ms
• 内存消耗：38MB
• 编程语言：typescript
• 解法介绍：dp[i]=dp[j]&&set.has(j,i-j)。

function wordBreak(s: string, wordDict: string[]): boolean {
  const len = s.length;
  const wordSet = new Set(wordDict);
  const dp = [true];
  for (let i = 1; i <= len; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && wordSet.has(s.substr(j, i - j))) {
        dp[i] = true;
        break;
      }
  return dp[len] ? dp[len] : false;
}