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));
  라는 조건을 주어 재귀로 풀 수도 있다.