문제
문제 : https://leetcode.com/problems/is-subsequence/?envType=study-plan-v2&envId=leetcode-75
문자열 s, t가 주어질 때 s가 T의 하위 문자열이면 True를 반환하고, 하위 문자열이 아니면 False를 반환하는 프로그램을 작성하라.
여기서 하위 문자열이란, 나머지 문자의 상대적인 위치를 방해하지 않고 일부 문자열을 삭제하여 원래 문자열에서 형성되는 새로운 문자열을 말한다.
예시 )
- s가 abc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이다.
- s가 axc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이 아니다.
풀이
정규표현식 패턴을 만들어, t가 패턴에 일치하는지 확인하는 방식으로 구현했다.
예로 들어 s가 abc일 때 그 패턴은 a.*b.*c가 된다. 각 문자 사이에는 문자열이 포함될 수도 있고, 포함되지 않을 수도 있기 때문에 패턴에 일치하는 문자열은 하위 문자열이라고 판단할 수 있다.
import re
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# 패턴 생성
pattern = ".*".join(list(s))
# 일치 여부 반환
return re.search(pattern, t) is not None
다른 풀이
정규표현식이 아니라 포인터를 사용한 다른 사람의 풀이도 적어둔다.
방법은 다음과 같다.
- 문자열 s, t 각각에 포인터를 사용한다.
- t의 포인터를 사용해 t를 순회한다.
- t의 문자가 s 문자와 일치하면 s 포인터를 이동시킨다.
- s 포인터가 s 문자열의 끝을 가리키면 t는 s의 하위 문자열이다.
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
참고 문서
https://leetcode.com/problems/is-subsequence/?envType=study-plan-v2&envId=leetcode-75
728x90