Leetcode - 392. Is Subsequence

문제

첫번째 문자열이 두번째 문자열의 subsequence인지 판단하기

Input: s = "abc", t = "ahbgdc"
Output: true

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

해결 O(t)

06/07

bool isSubsequence(char *s, char *t){
    int tsize = strlen(t);
    if (*s == '\0' && *t == '\0')
        return true;
    for (int i = 0; i < tsize; i++) {
        if (*s == t[i])
            *s++;
        if (*s == '\0')
            return true;
    }
    return false;
}

07/25 다시 풀었는데 잘 못풀었음.

해결 O(t)

Two Pointer로 해결. 투포인터는 어떤 조건에서 left 와 right 포인터를 증가시킬지 조건을 먼저 따져보는게 우선. 위의 코드보다 이 코드가 더 간결함.

• s_idx 증가 하는 조건
  s[s_idx] == t[t_idx] 일 경우
• t_idx 증가 하는 조건
  기본적으로 t를 순회하므로 루프에서 항상 증가

bool isSubsequence(char *s, char *t) {
    int s_size = strlen(s);
    int t_size = strlen(t);
    int s_idx = 0, t_idx = 0;
    
    while (s_idx < s_size && t_idx < t_size) {
        if (s[s_idx] == t[t_idx])
            s_idx++;
        t_idx++;
    }
    if (s_idx == s_size)
        return true;
    return false;
}

리턴하는 부분을 이렇게 수정해도됨.

    return s_idx == s_size;