[LeetCode] 392. Is Subsequenc [Java]

 

알고리즘 분류: 파싱

문제 링크: https://leetcode.com/problems/is-subsequence/description/

 

【 문제 】

 

• 문자열 s와 t의 subsequence 인지 확인하는 문제이다.

 

【 풀이 】

 

1. 문자열 s와 t의 길이가 0이면 true를 반환한다.
2. 문자열 t를 순회하면서, s의 문자와 같은 문자가 나오면 idx를 증가 시킨다.
3. idx가 s의 길이와 같아지면 s가 t의 subsequence 임을 의미하므로, true를 반환한다.
4. t를 모두 순회했을 때, idx가 s의 길이와 같아지지 않으면 false를 반환한다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

 

 

【 코드 】

public class LeetCode_392 {
    public boolean isSubsequence(String s, String t) {
        int idx = 0;
        if (s.isEmpty()) {
            return true;
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == s.charAt(idx)) {
                idx++;
            }
            if (idx == s.length()) {
                return true;
            }
        }
        return false;
    }
}