C++ 392. Is Subsequence(Leet Code)

Leet Code_392. Is Subsequence

Dynamic Programming

 

https://leetcode.com/problems/is-subsequence/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

string안에 Subsequence가능한지 확인하기

​

방법

1. sub에 순서가 맞아야함

 

결과

string안에 Subsequence가능한지 확인하기

 

통과한 코드

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int nMax = INT_MIN;
        string str = "";
        for (int i = 0; i < s.size(); i++)
        {
            int nIndex = t.find(s[i], 0);
            if (nIndex < 0)
                return false;
            else
            {
                if (nMax > nIndex && str.find(s[i]) == -1)
                    return false;
                t.erase(nIndex, 1);
                str += s[i];

            }
            nMax = nIndex;
        }
    return true;
            
    }
};

음..뭔가 DP로 풀지 않은거 같다

 

 

다른 사람 코드

class Solution {
public:
    bool isSubsequence(string s, string t) {
		
        int idx=0;
        for(char c:t) 
            if(s[idx]==c) idx++;
        
        return idx==s.size();
    
    }
};

있을 때만 넘어가면서 총 크기랑 같으면 true로 리턴하기

혼란하다 혼란해..