139. Word Break

두가지 컨셉으로 접근할 수 있다.

첫째. BFS
인덱스 0부터 시작해서 특정 단어의 마지막 인덱스보다 1큰값을 큐에 넣어주면서 bfs진행

const wordBreak = function(s, wordDict) {
    const set = new Set(wordDict);
    const visited = new Set()
    const q = [0]
    while (q.length) {
        const start = q.shift()
        if (!visited.has(start)) {
            for (let end = start + 1; end <= s.length; end++) {
                if (set.has(s.slice(start, end))) {
                    if (end === s.length) return true;
                    q.push(end)
                }
            }
            visited.add(start)
        }
    }
    return false
};

둘째. dynamic programming

투포인터를 활용해서 그 단어가 단어리스트에 존재하면 table에 체크하면서 전진

const wordBreak = (s, wordDict) => {
  if (wordDict == null || wordDict.length === 0) return false;

  const set = new Set(wordDict);
  const dp = Array(s.length + 1).fill(false);
  dp[0] = true;

  for (let end = 1; end <= s.length; end++) {
    for (let start = 0; start < end; start++) {
      const w = s.slice(start, end);
      if (dp[start] === true && set.has(w)) {
        dp[end] = true;
        break;
      }
    }
  }
  return dp[s.length];
};