[LeetCode] In Subsequence

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75

 

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

 

Example 1:

Input: s = "abc", t = "ahbgdc"

Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"

Output: false

 

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 104
• s and t consist only of lowercase English letters.

 

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

 

 

짧은 문자열과 긴 문자열, 두 개의 문자열이 주어진다.

이 때 긴 문자열 안에서 짧은 문자열 내 하나 하나의 문자가 순서대로 모두 포함되어 있으면 true, 아니면 false를 리턴해야 한다.

 

 

문제 풀이

function isSubsequence(short: string, long: string): boolean {
    let result = false;
    const shortArr = short.split("");
    const longArr = long.split("");
    longArr.map((str)=>{
        if(shortArr.length === 0){
            return true;
        }
        if(str === shortArr[0]){
            shortArr.shift();
        }
    })
    return shortArr.length === 0;
};

 

짧은 문자열과 긴 문자열을 각각 배열로 split한 뒤, map 내에서 짧은 문자열의 현재 문자가 나오면 그 엘리먼트를 빼 주었다.

그리고 끝까지 돌고 난 후에 shorArr의 길이가 0이면 true, 아니면 false를 리턴한다.

longArr을 다 돌기 전에 이미 shortArr의 길이가 0이 되면 더 이상 돌지 않고 true를 리턴한다.

 

하지만 이 문제가.. Two Pointers 라는 카테고리 내에 있던 문제라ㅋㅋㅋ 내가 푼 방식은 엄밀하게 따지면 좀 결이 다른 것 같다.

 

참고용 다른 풀이 첨부

var isSubsequence = function(s, t) {
    let sp = 0;
    let tp = 0;

    while (sp < s.length && tp < t.length) {
        if (s[sp] === t[tp]) {
            sp++;
        }
        tp++;
    }

    return sp === s.length;    
};

https://leetcode.com/problems/is-subsequence/solutions/5101957/video-two-pointer-solution/?envType=study-plan-v2&envId=leetcode-75