Description:

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

생각 과정

문제 파악

문자열 s와 문자열 배열 wordDict가 주어지면, s가 wordDict의 원소들로 분할 가능한지 확인하는 문제이다. wordDict의 원소는 여러번 사용될 수 있으며, 특정 원소가 사용되지 않아도 분할만 되면 괜찮다.

일반적인 사고 방식

• wordDict의 한 문자열이 s에 포함되어 있는지 확인하고, s에서 해당 문자열을 제거한다.
  -> s에 포함될 수 있는 방법이 여러 개라면, 모든 방법을 확인한다.
  
  
• 이 행위를 반복하여 wordDict의 모든 원소를 확인했을 때, s에 남아있는 문자가 없다면 s는 wordDict의 원소로 분할가능하다.

코딩으로 다듬기

문자열 s의 글자를 순회하며 wordDict의 원소와 같은지 확인한다. s가 wordDict의 원소들로 분할 가능한 1개 이상의 경우의 수가 존재하면 true를 반환한다.

• s의 길이와 같은 크기의 배열 table을 생성한다.
• table의 0번 인덱스는 true
• table의 인덱스는 s의 해당 인덱스까지의 문자열이 wordDict의 원소로 분할되어지면(부분 문자열이 wordDict의 원소와 같음), true를 저장한다.

• s의 i번째 인덱스부터 wordDict의 원소의 length 크기의 문자열이 해당 원소와 같은지 확인한다.
• 같다면 table[ i + wordDict원소의 length ] = true
• table[s.length]에 true가 저장된다면 s 전체가 wordDict로 분할 가능하므로 true를 반환한다.

풀이 코드

var wordBreak = function (s, wordDict) {
  let table = [true];

  for (let i = 0; i <= s.length; i++) {
    if (table[i]) {
      for (let word of wordDict) {
        if (s.slice(i, i + word.length) === word) {
          table[i + word.length] = true;
        }
      }
    }
  }
  return table[s.length] ? table[s.length] : false;
};