[Leetcode/TwoPointer] 2825. Make String a Subsequence Using Cyclic Increments

첫번째 방법

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i, j = 0, 0  # 두 문자열을 비교할 포인터
        
        while i < len(str1) and j < len(str2):
            # 현재 str1[i]가 str2[j]와 같거나, 다음 문자로 변환 가능하면 진행
            if str1[i] == str2[j] or chr((ord(str1[i]) - ord('a') + 1) % 26 + ord('a')) == str2[j]:
                j += 1  # str2의 다음 문자로 이동
            i += 1  # str1의 다음 문자로 이동
        
        # str2의 모든 문자를 순서대로 찾을 수 있으면 부분 수열
        return j == len(str2)

코드 설명

1. 투 포인터 접근법 (i, j 사용)
   • i: str1을 탐색하는 포인터
   • j: str2를 탐색하는 포인터
2. 문자 비교
   • str1[i] == str2[j]: 그대로 유지 가능
   • str1[i]가 str2[j]의 바로 이전 문자인지 확인
     • (ord(str1[i]) - ord('a') + 1) % 26 + ord('a') == ord(str2[j])
     • 이 조건이 참이면 str1[i]를 변환하여 str2[j]로 만들 수 있음.
     • 26이 나오는 이유는 알파벳이 26개 존재하기 때문.
       문자를 다음 문자로 바꿀 때, 'z' → 'a' 처럼 순환 구조(cyclic) 처리를 해야 하기 때문에 모듈로 연산(% 26) 을 사용.
3. 부분 수열 여부 확인
   • j == len(str2): str2의 모든 문자를 찾았으면 True 반환.
   • 그렇지 않으면 False.

---

함수 설명 - chr(), ord()

chr()와 ord()는 문자와 숫자(유니코드) 간 변환을 수행하는 함수.

1️⃣ ord(char) → 문자를 숫자로 변환

ord('a')  # 97
ord('A')  # 65
ord('z')  # 122

• ord(char)는 문자를 해당 유니코드(ASCII) 정수값으로 변환.
• 예를 들어 'a'는 97, 'A'는 65, 'z'는 122.

2️⃣ chr(int) → 숫자를 문자로 변환

chr(97)   # 'a'
chr(65)   # 'A'
chr(122)  # 'z'

• chr(int)는 유니코드 정수를 해당 문자로 변환.
• 예를 들어 97은 'a', 65는 'A', 122는 'z'.

---

시간 복잡도 분석

• while 루프는 최대 O(N + M) (N: str1 길이, M: str2 길이).
• 각 문자를 한 번씩만 비교하므로 O(N).
• 따라서, 시간 복잡도는 O(N), 공간 복잡도는 O(1) (추가 공간 사용 없음).

---

두번째 방법 -> help function 활용

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        def next_char(c):
            return 'a' if c == 'z' else chr(ord(c) + 1)  # 'z' → 'a', 나머지는 +1
        
        i, j = 0, 0  # 두 문자열의 포인터
        
        while i < len(str1) and j < len(str2):
            # str1[i]가 str2[j]와 같거나, 변환 후 같다면 진행
            if str1[i] == str2[j] or next_char(str1[i]) == str2[j]:
                j += 1  # str2의 다음 문자 탐색
            i += 1  # str1의 다음 문자 탐색
        
        return j == len(str2)  # 모든 문자를 찾으면 True, 아니면 False

 

26을 사용하지 않고 다음 문자로 변경하는 방법도 가능함!
Python의 chr()와 ord() 함수를 활용해서 'z'를 'a'로 변환하는 로직을 단순화할 수 있음.