[LeetCode] Is Subsequence

Is Subsequence

문제

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 >= 10⁹, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

고민

해당 문제에서 제일 먼저 확인해야할 것은 "subsequence"가 무엇인가이다.
subsequence는 문자의 순서는 유지하면서 중간의 몇 글자 생략해 만든 문자열이다.

그렇다면 문제를 풀 때 중간에 문자를 건너뛰어도 되지만, 원래 순서는 유지되어야한다.

비교작업을 해야하니 이중for문을 사용해서 하면 될것 같은데...

1. t 기준으로 돌기
2. s 기준으로 돌기
   이 두가지 방법을 모두 사용했으나 순서(인덱스)를 정확히 파악하는 것이 어려웠다.

해결 코드를 확인 후 고민 정리를 더 해야겠다.

해결

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        var sIndex = 0
        var tIndex = 0
        while (sIndex < s.length && tIndex < t.length) {
            if (s[sIndex] == t[tIndex]) {
                sIndex++
                tIndex++
            } else {
                tIndex++
            }
        }
        return sIndex == s.length
    }
}

앞서 내가 고민했던 index 처리를 어떻게 해야하는가에 고민을 많이했다.
답은 이중 for 문이 아니라, 두개의 index를 공통으로 확인하고 비교를 해야했다.
s의 char 와 t의 char 가 같으면 같은 index이고,
다르다면 건너뛰어야하기때문에 t의 char 를 확인할 수 있는 tIndex만 증감하였다.

그럼 결국 return 되는 값은, 정상적으로 t 문자열에 s문자열이 포함이 되었다면 sIndex는 다 증감되었을 테니,
s 문자열 길이와 동일하게 된다.

결과