392. Is Subsequence

392. Is Subsequence

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

문제

풀이(처음 푼 코드)

처음 풀었을 때 2중 for문으로 최대한 최적화하는 방향으로 생각하였다.
(첫 번째 최적화 - 동적으로 for문 줄이기)
Example 1으로 설명하자면 s = "abc"에서 "b"를 체크하는 것을 생각해보자. t = "ahbgdc"에서 b가 있으면 다음 for문 돌 때 처음부터 시작하는 것이 아니라 b+1 위치인 "g"인덱스부터 시작하는 것이다.
(두 번째 최적화 - 만약 문자열 s 체크를 끝내면 바로 return True 해주기)
만약 s = "abc"이고 t = "abcdefg"라 가정해 보자
s에서 "c"를 체크하고자 할 때 t에서 "c"체크 후 이후에 문자열을 체크해 줄 필요 없기에 바로 return 해준다.

아무래도 중첩for문이라 시간복잡도는 (N^2)이지만 최적화를 통해 Accept는 되었다.

풀이(시간복잡도 N으로 바꾼 로직)