[LeetCode] 392. Is Subsequence

 

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

Is Subsequence - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Easy

 

문제

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).

 

문자열 s와 t가 주어진다. s가 t의 부분문자열인지 구하여라.

(단, 부분문자열의 문자 순서는 원래 문자열의 문자 순서를 따라야 한다. 즉, "ace"는 "abcde"의 부분문자열이지만, "aec"는 아니다.)

 

풀이

나는 s를 큐에 넣고, t의 요소에서 발견되면 s에서 pop하는 방법으로, t를 다 순회하기 전까지 큐를 빼지 못하면 false를 반환하는 방법으로 하였다.

 

그러나, 투 포인터를 사용한 솔루션도 알게 되었고, 이 방법이 더 빠른 성능을 보여줌을 알 수 있었다.

 

코드(C++)

class Solution {
public:
    bool isSubsequence(string s, string t) {
        deque<char> dq;
        int idx = 0;
        if(s.size() > t.size()) return false;
        for(int i = 0; i < s.size(); i++){
            dq.push_back(s[i]);
        }
        while(!dq.empty()){
            if(idx >= t.size()) return false;
            if(dq.front() == t.at(idx)){
                dq.pop_front();
            }
            idx++;
        }
        return true;
    }
};

 

아래는 다른 사람의 개선된 코드이다.

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.length(),m=t.length();
        int j = 0; 
    // For index of s (or subsequence
 
    // Traverse s and t, and
    // compare current character
    // of s with first unmatched char
    // of t, if matched
    // then move ahead in s
    for (int i = 0; i < m and j < n; i++)
        if (s[j] == t[i])
            j++;
 
    // If all characters of s were found in t
    return (j == n);
    }
};