[28일차] Multiple Pointers 2

저요·2022년 10월 19일

2022 100th day challenge

목록 보기

28/97

문제

Multiple Pointers - 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.

Examples
isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)
Your solution MUST have AT LEAST the following complexities
Time Complexity - O(N + M)
Space Complexity - O(1)

해결책

본격적으로 들어가기 전에...

두 개의 문자열을 받아 같은 순번으로 문자열이 존재하는지를 파악하는 문제이다.
다중포인터를 사용해서 문제를 풀어야 하는데, 나는 str1에 포인터를 하나, 그리고 str2에 포인터를 하나 두고 비교하며 움직이는 것으로 문제를 풀었다. 내가 작성한 해결책은 아래와 같다.

Solution

function isSubsequence(str1, str2) {
    let first = 0; 
    let second = 0;

    for(let i = 0; second < str2.length; i++){
        //문자가 같으면 str1의 포인터를 이동
        if(str1[first] === str2[second]){
            first++;
        }else{
            //같지 않으면 str의 포인터를 이동
            second++;
        }
    }

    //str1의 포인터가 모두 이동했는지 확인.
    if(first === str1.length){
        return true;
    }else{
        return false;
    }
  
}

문제에서 최소 O(N+M) 의 시간복잡도와 O(1)의 공간복잡도의 알고리즘을 작성할 것을 요구하고 있다.
처음 생각해낸 솔루션에서는 문자열을 배열로 .split()하려고 했으나, 그러면 요구한 공간 복잡도에 어긋나 고민하고 있었다. 그러다 검색하던 중 문자열을 배열처럼 사용할 수 있다는 것을 알게 되었고 그 자료구조의 특징을 이용해서 문제를 풀었다.