[Leetcode] 30. Substring with Concatenation of All Words - JS
1. 문제 분석
문제분석
--------------------
- 문자열 s, 문자열 배열 words가 주어진다.
- words 배열 속 문자열은 동일한 길이를 가진다.
- words 배열 속 단어들을 순서를 바꿔서 연결한 단어를 s가 부분 문자열로 포함하고 있는지 확인한다.
예를 들어, s = "barfoothefoobarman", words = ["foo","bar"]
words로 가능한 단어들은 'foobar', 'barfoo'가 있는데,
s의 0번째 인덱스에 'barfoo'
s의 9번째 인덱스에 'foobar'가 있으므로 [0, 9]를 반환한다.
- 인덱스의 순서는 상관없이 반환해도 된다.
제한조건
--------------------
- 1 <= s.length <= 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- s, words[i]는 영어 소문자로 구성된다.
2. 접근 방법
접근방법 - Sliding Window & Hash Map
--------------------
0. 초기값 설정
- 각 단어의 빈도수를 hashMap에 저장한다.
- wordsCount = words 배열의 길이, wordsLength = words 배열 요소의 길이를 초기화한다.
- res = [] 결과값 리스트 초기화한다.
1. hashMap에 단어 빈도수 추가
나중에 window 크기별로 쪼개서 중첩 반복문 순회 시 window 내부의 단어들의 빈도수를 세었을 때,
words에 포함된 단어의 빈도수 보다 많아지면 부분 문자열이 될 수 없음을 판단할 수 있다.
2. window 크기에 맞게 s 문자열 시작 인덱스부터 반복문 순회한다.
window 크기는 모든 단어의 길이가 동일하므로 단어 갯수 * 단어 길이이다.
예를 들어, words = ['foo', 'bar']라면 window의 크기는 'foobar', 'barfoo'
이렇게만 가능하므로 2 * 3 = 6이된다.
window 크기를 기준으로 s 문자열 시작 인덱스부터 한칸씩 우측으로 이동하면서 비교할 것이다.
3. window 안에 존재하는 단어 갯수만큼 반복문 순회한다.
window = 'foobar' 혹은 'barfoo' 이런 단어 조합들 중 하나이다.
window를 직접 비교할 것이 아니므로... window를 정확한 단어로 특정하지 않는다.
어찌됐든 window에는 words의 단어들을 1번씩 사용해서 구성했다는 것을 확실하다.
window 내부에서 words 갯수만큼 반복문 순회하면서 순열로 조합된 단어가 포함될 수 없는 조건들을 나열하고
해당 조건들에 부합하지 않았을 경우 그 때의 시작 인덱스(i)를 결과값에 추가한다.
즉, 우리는 순열로 조합된 단어 리스트를 직접 모두 구하지 않고 해당 단어들의 빈도 수가 일치하는지만 따져서
시작 인덱스를 구할 것이다.
처음 문제를 접했을 때는 순열을 사용하여 순서가 의미있는 단어 조합 리스트를 구하였지만, 직접 단어 조합 리스트를 구하는 작업을 하지 않아도 몇가지 조건을 통해 시작 인덱스를 기준으로 window 크기만큼만 확인하여 참, 거짓으로 판단할 수 있다.
우선 위 내용을 한번 읽어보고 코드를 이해해보자.
첫번째 nextWord = 'bar'
✅ 'bar'는 frequency에 존재한다.
wordsSeen = { 'bar': 1 }
✅ wordsSeen[bar]가 frequency[bar]보다 크지 않다.
두번째 nextWord = 'foo'
✅ 'foo'는 frequency에 존재한다.
wordsSeen = { 'bar': 1, 'foo': 1 }
✅ wordsSeen['foo']가 frequency['foo']보다 크지 않다.
window 크기만큼 짤라서 그 안의 단어들이 조건에 모두 부합하므로 해당 시작 인덱스를 조건에 부합한다.
3. 코드
var findSubstring = function(s, words) {
// 초기값 설정
const frequency = {};
const wordsCount = words.length;
const wordsLength = words[0].length;
const res = [];
// words 배열의 단어 빈도수 세기
for (const c of words) {
frequency[c] = (frequency[c] || 0) + 1;
}
// sliding window + hash map
for (let i = 0; i <= s.length - (wordsCount * wordsLength); i++) {
const wordsSeen = {};
for (let j = 0; j < wordsCount; j++) {
const nextWordIndex = i + j * wordsLength;
const nextWord = s.slice(nextWordIndex, nextWordIndex + wordsLength);
if (!(nextWord in frequency)) {
break;
}
wordsSeen[nextWord] = (wordsSeen[nextWord] || 0) + 1;
if (wordsSeen[nextWord] > frequency[nextWord]) {
break;
}
if (j + 1 === wordsCount) {
res.push(i);
}
}
}
return res;
};
빈도수 세는 것까지는 이해가 됐으리라 생각하고, sliding window + hash map 부분부터 이해해보자.
시작 인덱스 i를 기준으로 window 크기만큼 한칸씩 이동하면서 비교할 것이므로
반복문 종료 시점은 s.length - (wordsCount * wordsLength)까지로 정한다. 왜냐하면 window가 s의 길이를 벗어난 경우를 고려할 필요가 없기 때문이다.
window를 비교하는 반복문이 실행될 때마다 해당 window에 등장한 단어들의 빈도수를 저장하기 위한 wordsSeen 객체를 선언한다.
window에서 words 요소의 길이만큼 단어를 잘라서 비교할 것이다.
잘린 단어는 nextWord 라는 변수에 할당한다.
1. nextWord 가 frequency 객체에 존재하는가?
만약 frequency 객체에 존재하지 않는다면, words 배열로 만들 수 없으므로 pass 한다.
2. wordsSeen에 빈도수 추가한 후 wordsSeen에 등장한 빈도가 frequency에서 등장한 빈도보다 많은가?
window 내부에서 등장한 단어(nextWord)의 빈도수가 words 배열에서 등장한 빈도수 보다 많다는 것은 words 배열을 모두 사용해도 불가능하므로 pass 한다.
window에 모든 nextWord를 확인했을 때, 1번과 2번 조건에 부합하지 않고 window의 마지막 반복문 순회까지 도달했으면 해당 시작 인덱스에서 words로 순열 조합된 단어가 존재한다는 의미와 부합하므로 이 때의 시작 인덱스를 의미하는 i를 결과 배열에 추가한다.
4. 복잡도 분석
- 시간복잡도: O(n^2)
- 공간복잡도: O(m)
공간복잡도 O(m)은 words 리스트의 길이 만큼 공간을 차지하게 된다.
words 단어 리스트를 순열로 합친 단어 리스트를 가지고 s 문자열에 indexOf를 사용하여 등장한 모든 인덱스를 찾는 방법을 택하였지만 순열로 합칠 때, DFS를 재귀를 통해 구현했고 이 때 words 길이가 길어졌을 때 시간 초과가 발생하는 문제가 있었다.
다른 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였고, sliding window + hash map을 사용하여 window 크기만큼의 단어들의 빈도수를 비교하여 순열로 합친 단어가 존재할 수 있는지를 판단하는 방법을 공부했다.