leetcode
139. Word Break 자바스크립트 DP
냠냠맨
2023. 1. 8. 20:21
⚡문제정보
영어라 곤란하지만 문제 자체는 굉장히 심플합니다.
문자열 s와 문자열요소로 이루어진 배열 wordDict가 주어지는데
wordDict에 있는 단어를 재사용해도 상관없으니까 사용해서 s를 만들 수 있냐?
할 수 있으면 true 없으면 false를 반환해라
근데 여기서
🙄제한사항
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
이런식으로 wordDict의 단어들을 누더기처럼 이어붙이면 s를 만들 수는 있는데
공백없이 이전에 썻던 알파벳을 중복 사용해서 쓰면 안된다. 라고 이해할 수 있을듯
🔍접근방법
저는 못 풀었고요 답지 봤습니다.
이 두분의 코드를 참고해서 작성했습니다.
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에서 문자를 찾아볼수 있느냐
문자의 앞부분부터 접근하느냐만 차이가 있는 풀이입니다.
반응형