isSubsequence 문제풀이
내 풀이
/*
문제
Write a function called isSubsequence
which takes in two strings and checks
whether the characters in the first string
form a subsequence of the characters in the second string.
In other words, the function should check
whether the characters in the first string
appear somewhere in the second string,
without their order changing.
Your solution MUST have AT LEAST the following complexities:
Time Complexity - O(N + M)
Space Complexity - O(1)
*/
function isSubsequence(a, b) {
let idxA = 0;
let idxB = 0;
while (idxA < a.length && idxB < b.length) {
if (a[idxA] === b[idxB]) {
idxA++;
idxB++;
} else {
idxB++;
}
}
if (idxA === a.length) {
return true;
} else {
return false;
}
}
console.log(isSubsequence('hello', 'hello world')); // true
console.log(isSubsequence('sing', 'sting')); // true
console.log(isSubsequence('abc', 'abracadabra')); // true
console.log(isSubsequence('abc', 'acb')); // false (order matters)
해설
- 인덱스를 움직이며 풀었다.
- while문 탈출시에 idxA가 a.length와 같다면 모든 단어를 포함했다는 뜻 -> true
- 아니라면 false
- 재귀로 풀 수도 있다.
- 비교시에 값이
- 같을 때: return isSubsequence(a.slice(1), b.slice(1));
- 다를 때: return isSubsequence(a, b.slice(1));
라는 조건을 주어 재귀로 풀 수도 있다.
Author And Source
이 문제에 관하여(isSubsequence 문제풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@stthunderl/isSubsequence-문제풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)