Post List

[leetcode] Is Subsequence

날짜:
링크: https://leetcode.com/problems/is-subsequence/

문자열 s, t가 주어졌을 때 s가 t의 부분을 이루는지 맞히는 문제.
얼마 전 스킬트리라는 프로그래머스 문제를 보다가 아이디어를 얻었다.

s를 순회하며, s의 한 문자를 t에서 찾을 수 있는지 체크해주면 된다. 단, t에서 찾기 시작할 인덱스는 한번 찾았을 때보다 1 높아야 한다.

코드:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
using namespace std;

class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        int next = -1;

        for (auto i : s)
        {
            int pos = t.find(i, next + 1);
            if (pos == -1)
            {
                return false;
            }
            if (pos >= next)
            {
                next = pos;
            }
            else
                return false;
        }
        return true;
    }
};

댓글

댓글 쓰기