139. Word Break

문제링크: https://leetcode.com/problems/word-break/

s 를 wordDict의 문자들로 나눌 수 있는지 알아내는 문제다. (중복해서 사용 가능)

Solution

Dynamic programming

s[i]까지의 문자열이 단어로 만들어질 수 있다면 s[i] + wordDict의 단어 도 만들 수 있다. 이렇게 s[i]까지 문자열이 가능한지 여부를 저장하는 배열을 만들고 앞에서 부터 갱신해 끝 문자열까지 가능한지를 얻어낼 수 있다.

Algorithm

• wordDict을 Set으로 만들고, 가장 긴 단어의 길이를 구한다.
• breakable이라는 배열을 만들고 이는 s[i]까지의 문자열이 단어로 분할되는지 여부를 저장한다.
• i = 0부터 s.slice(0, i + 1) 까지의 문자열이 breakable한지 확인한다.
• 확인하는 방법은 breakable[j - 1] 이 true고 s.slice(j, i + 1)이 wordDict에 존재한다면 가능한 문자열이다.

var wordBreak = function(s, wordDict) {
  const mySet = new Set();
  let maxLength = 0;
  for (let el of wordDict) {
    mySet.add(el);
    maxLength = Math.max(maxLength, el.length);
  }  

  // 단어 길이는 최대 maxLength 이므로 index - maxLength 까지 중에 true 인것에 wordDict의 단어로 완성되는 경우 true로 변경
  const breakable = new Array(s.length).fill(false);
  for (let i = 0; i < s.length; i++) {
    // s[i]까지 단어를 만들 수 있는지 확인해서 breakable[i]를 true로 변경
    for (let j = Math.max(0, i - maxLength + 1); j <= i; j++) {
      if (j === 0 || breakable[j - 1]) {
        if (mySet.has(s.slice(j, i + 1))) {
          breakable[i] = true;
          break;
        }
      }
    }
  }
  return breakable[s.length - 1];
};

• s를 순서대로 탐색하는데 O(n)
• 각 i에서 i - maxLength + 1까지 나눠서 탐색하는데 O(maxLength)
• s.slice(j, i + 1) 하는데 최대 O(maxLength / 2)가 걸린다.

따라서 총 O(n * maxLength^2)이고 maxLength 의 최대값은 20이다.