[Two Pointer] 392. Is Subsequence

https://leetcode.com/contest/leetcode-weekly-contest-3/problems/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 <= 104
• s and t consist only of lowercase English letters.

 

---

 

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        #s를 split 후 t를 앞에서부터 순회하면서 찾다가 일치하면 다음 탐색 (대신 인덱스도 위치도 동일하게)
        
        i, j = 0, 0 #포인터 초기화
        
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
                
        #true, false만 반환하므로 i가 전체 s의 길이와 동일할 때까지 증가하면 모두 찾았다는 의미
        return i == len(s) #True

 

---

 

while i < len(s) and j < len(t):

1. s의 길이가 남아있는 동안만 t를 순회하도록 1차로 걸 수 있는 조건

 

 

            if s[i] == t[j]:
                i += 1
            j += 1

2. 일치할 경우 둘다 인덱스 +1부터 시작하도록 거는 조건

 

👩‍🌾j 인덱스를 증가시키는 로직을 i의 증가 로직과 다른 들여쓰기 수준에서 진행하는 이유

 

1. i 인덱스 관리: i 인덱스는 문자열 s의 문자가 문자열 t에서 일치할 때만 증가한다. 문자열 s의 다음 문자를 찾기 위해 t에서 계속 탐색을 진행해야 함을 의미한다.

 

2. j 인덱스 관리: j는 문자열 t를 순회하는 인덱스로서, 문자열 t의 모든 문자를 확인하면서 s의 문자와 일치하는지 여부를 각 위치에서 검사하는데, j 인덱스의 증가는 조건과 무관하게 항상 일어나야 한다.

따라서 if 문의 외부에서 처리되어 t의 각 문자를 확인할 때마다 j가 무조건 1씩 증가해야 한다.