139. Word Break 자바스크립트 DP

⚡문제정보

 

 

영어라 곤란하지만 문제 자체는 굉장히 심플합니다.

문자열 s와 문자열요소로 이루어진 배열 wordDict가 주어지는데

wordDict에 있는 단어를 재사용해도 상관없으니까 사용해서 s를 만들 수 있냐? 

할 수 있으면 true 없으면 false를 반환해라

근데 여기서

---

 

🙄제한사항

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

 

이런식으로 wordDict의 단어들을 누더기처럼 이어붙이면 s를 만들 수는 있는데

공백없이 이전에 썻던 알파벳을 중복 사용해서 쓰면 안된다. 라고 이해할 수 있을듯

 

---

 

 

🔍접근방법

 

저는 못 풀었고요 답지 봤습니다.

https://leetcode.com/problems/word-break/solutions/2483845/clean-and-well-structured-javascript-implementation-top-99-8/?languageTags=javascript 

https://leetcode.com/problems/word-break/solutions/2604650/javascript-dp-solution-71-ms/?languageTags=javascript 

 

이 두분의 코드를 참고해서 작성했습니다.

 

1. Set 자료구조를 활용한다.

2. dp를 사용한다.

 

---

 

 

🔍다른 사람의 풀이

 

let wordBreak = function (s, wordDict) {
  let arr = new Array(s.length + 1).fill(false);
  arr[s.length] = true;
  for (i = s.length - 1; i >= 0; i--) {
    for (const word of wordDict) {
      if (
        i + word.length <= s.length &&
        s.substring(i, i + word.length) === word) {
        arr[i] = arr[i + word.length];
      }
      if (arr[i]) break;
    }
  }
  return arr[0];
};

코드 설명은 다음과 같습니다.

let wordBreak = function (s, wordDict) {
  let arr = new Array(s.length + 1).fill(false);
  arr[s.length] = true;
  /*
s의 길이 +1만큼을 false로 채워줍니다.
배열의 마지막 부분은 true로 설정해줍니다.
*/

  for (i = s.length - 1; i >= 0; i--) {
    /*
    주어진 문자열의 뒷부분부터 앞으로 순회해나갑니다
    */
    for (const word of wordDict) {
      if (
        i + word.length <= s.length &&
        s.substring(i, i + word.length) === word
      ) {
        /*
    각 요소를 기준으로 s의 일부분을 추출해서 추출한 부분과 요소가 같은지 검사합니다.
    첫번째 순회에서 i는 7이고 word의 길이는 4입니다.

    따라서 첫 순회에서 s.substring(7,11)은 e입니다.
    i를 깎아주면서 쭉 순회하다보면 if 케이스를 만족하는 경우를 만나게됩니다.
    위 테스트케이스에선 i=4, word = "code"일때 arr[4 + 4]의 값인 true가 arr[i]에 할당됩니다
    
    모든 단어는 공백시퀀스를 기준으로 구분되어야하고 단어를 재사용할 수 있기때문에
    일치하는 단어가 있는 경우 true로 만들어주는게 아니라
    공백시퀀스를 기준으로 만들어주기 위해서 번거롭게 i + word.length를 해줍니다.
    
    이 경우 arr[4]는 true가 되고 이후 i가 0에 도달했을때
    arr[0] = arr[4]의 값 true가 할당되어
    arr[0]은 true가 됩니다.

    */

        arr[i] = arr[i + word.length];
      }

      if (arr[i]) break;
      // arr[i]가 true가 되었다면 더이상 순회할 필요가 없으므로 break
    }
  }

  return arr[0];
  //만약 공백시퀀스를 지키면서 true가 계속 전파되어 배열의 맨 앞까지 true가 되었다면
  //true를 반환하고 그렇지 않다면 false를 반환합니다.
};

let string = "leetcode";
let wordDict = ["leet", "code"];
console.log(wordBreak(string, wordDict));

console.log(string.substring(8, 10));

 

---

 

🔍또다른 사람의 풀이

 

var wordBreak = function (s, wordDict) {
  const wordDictSet = new Set(wordDict);
  let dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i < s.length + 1; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] === true && wordDictSet.has(s.substring(j, i))) {
        dp[i] = true;
      }
      console.log(i, j, s.substring(j, i), dp);
    }
  }
  return dp[s.length];
};
let string = "leetcode";
let wordDict = ["leet", "code"];
console.log(wordBreak(string, wordDict));

/*
앞서 본 풀이는 배열의 뒷부분부터 순회해나가 dp[0]의 값을 반환하는 방식이었지만
위 풀이는 배열의 앞부분부터 순회하면서 dp의 마지막 부분 값을 반환하는 방식입니다

가장 큰 특징은 set 자료구조와 has()메서드를 이용해서 일치하는 단어를 뽑아오는데 소요되는
시간 복잡도를 O(1)로 만들어서 메모리,시간효율이 비약적으로 좋아졌습니다


*/

 

문제에 접근하는 개념 자체는 같지만

set을 통해 바로 wordDictSet에서 문자를 찾아볼수 있느냐

문자의 앞부분부터 접근하느냐만 차이가 있는 풀이입니다.