[LeetCode/easy/String] Is Subsequence

 

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

Is Subsequence - LeetCode

 

 

 

만약 s가 t의 subsequence라면 true

여기서 subsequence란, 원본 문자열에서 몇 개의 문자를 지웠더니 생성된 새로운 문자열이다.

bool isSubsequence(string s, string t) {
    int index = 0;
    for(int i=0; i<s.size(); i++){
        char cur = s[i];
        size_t pos = t.find(cur, index);
        if(pos == string::npos || pos < index) return false; //없는 경우 || 순서가 잘못된 경우
        t.erase(pos, 1); //알파벳이 여러개일수 있기 때문에 없애준다
        index = pos; //index 업데이트
    }
    return true;
}

index로 s문자열 인덱스를 관리한다. 

find 함수로 t문자열에 현재 가리키는 s의 원소가 있는지 확인하고 만약 없거나 있지만 앞에 있다면(잘못된 순서) false를 반환한다.

그런데 여기서 

"aaaaaa" "bbaaaa"와 같이 특정 알파벳이 여러 개일 수 있기 때문에 erase 함수로 없애준다.

 

---

 

 

또는 반복문으로 인덱스를 가리키는 방식을 사용해서도 할 수 있다. 

bool isSubsequence(string s, string t) {
    int sindex = 0;
    for(int tindex=0; tindex < t.size() && sindex < s.size(); tindex++){
        if(s[sindex] == t[tindex]) sindex++; //s값과 t값이 같다면 s의 인덱스를 가리키는 sindex++
    }
    return (sindex == s.size());
}

위의 코드는 for문으로 tindex를 loop를 따라 이동하게 하고 sindex의 경우 s와 t의 원소가 같은 경우에만 이동하도록 한다. 

반복문이 끝났을 경우, sindex가 s의 끝에 다다랐는지 확인하고 결과를 반환해준다. 

이렇게 하는 것이 더 빠르다...