392. Is Subsequence

[문제]

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

 

[TC]

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?

 

[접근]

실패한 방식의 접근은 "메모이제이션 + 인덱스 접근" 방식

Length 100 이 제약이라서 100개의 배열을 선언해놓고 찾은 인덱스를 넣는 메모이제이션 채택해서 활용.

추가로 찾은 문자는 앞에서 인덱스를 찾아서 erase 이렇게 밀리게 되는 인덱싱 숫자는 removecount 를 지울때마다 증가시켜 맨 처음 string 인덱스 위치에 맞도록 보정.

 

반례: 17 Case 의 s : Leeeetcode t : yyyy ~ l yyy ~ e ~ yyy ~ e ~ yyy ~ e ~ yyyyy ~ e ~ yyyyy ~ c ~ yyyy ~ o ~ yyyy ~ d ~ yyy e

 

총 y의 갯수가 9990 개라 총 만개의 문자열 사이에 l e e e e e c o d e 를 파묻음.

함정은 s 스트링의 e 가 4개, t 에는 e 가 5개 나는 4개를 지우고 마지막 1개의 e 와 code 의 e 가 남아서 find 로 체크하려했다가 못지운 e 의 인덱싱이 걸려서 false 가 나옴. 기댓값음 true

 

변경한 방식은 투포인터 접근 방식으로 진행

빈 string ret 을 선언한 후 같은 문자열이 나오면 하나씩 push_back , 같지 않으면 t 문자열을 증가. 

최종적으로 조건에 의해 나왔을때 ret == s 의 케이스라면 true 

 

[실패 코드] - 메모이제이션, 인덱스 접근

class Solution {
public: int removeCount = 0;
public: int removeIndex = 0;
public: int memory[100] = { 0, };
public:

    bool isSubsequence(string s, string t) {
        if ((s.size() == t.size()) && (s != t)) return false;

        for (int i = 0; i < s.size(); ++i)
        {
            int findIndex = t.find(s[i]);

            if (findIndex == -1)
                return false;

            if (removeIndex != 0 && memory[removeIndex - 1] > (removeCount + findIndex))
                return false;

            memory[removeIndex] = findIndex + removeCount;
            ++removeIndex;
            ++removeCount;

            t = t.erase(findIndex, 1);
        }

        return true;
    }
};

[성공 코드] - 투포인터 접근

class Solution {
    string ret;
public:

    bool isSubsequence(string s, string t) {
        if ((s.size() == t.size()) && (s != t)) return false;

        int sIndex = 0;
        int tIndex = 0;
        while (sIndex != s.size() && tIndex != t.size())
        {
            if (s[sIndex] == t[tIndex])
            {
                ret.push_back(s[sIndex]);
                ++sIndex;
                ++tIndex;
            }
            else
                ++tIndex;
        }

        if (ret == s) return true;

        return false;
    }
};

[결과]

[시도]

[후기]

넉넉히 잡아 20 ~ 30분이면 풀 수 있는 문제였다. 인덱싱 계산 고려를 하지않으면 10분 내외로 풀 수 있는 문제였으나, 

편하게 find 함수 + 메모이제이션 조합으로 풀려고 했다가 피본케이스다..

 

그냥 단순 무식하게 인덱스 비교 수행을 방향성잡고 진행했어도 충분히 10분 완료 케이스가 나올 수 있었는데 시간을 너무 잡아먹어서 아쉬운 문제.