[leetcode #392] Is Subsequence

Problem

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

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 <= 10⁴
・ 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?

Idea

주어진 문자열 s가 문자열 t의 subsequence인지 확인하는 문제다.

문자열 s의 문자를 하나씩 탐색하면서 t에 존재하는지 확인한다. 만약 문자가 있다면 index를 하나 올려 다음 문자를 해당 index부터 찾는 과정을 반복한다.

문자열 s의 모든 문자를 찾았다면 true를 리턴하고, 중간에 문자를 찾지 못했다면 false를 리턴한다.

Solution

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = 0;
        for (int i=0; i < s.length(); i++) {
            index = t.indexOf(s.charAt(i), index);
            if (index == -1) {
                return false;
            }
            index++;
        }

        return true;
    }
}

Reference

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