[Leetcode] 763. Partition Labels

문제

https://leetcode.com/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked

풀이

two pointer를 이용해서 first index와 last index를 갱신하며 푼 풀이는 다음과 같습니다.
이때, char별 최대 인덱스를 미리 한번만 계산해서 해시테이블에 저장해두는 과정을 통해 성능을 개선할 수 있습니다.(386ms -> 48ms)

from collections import defaultdict

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # char별 최대 인덱스를 hash table에 미리 계산해두기
        ch_max_idx = defaultdict(int)
        for i, ch in enumerate(s):
            ch_max_idx[ch] = max(ch_max_idx[ch], i)

        ans = []
        first_index = 0
        last_index = 0
        for i, ch in enumerate(s):
            # last_index 갱신
            last_index = max(last_index, ch_max_idx[ch])
            
            # 끝나는 위치면
            if i==last_index:
                ans.append(last_index-first_index+1)
                first_index = i+1
                last_index = i+1
        
        return ans

아래는 해시테이블 적용 전 코드입니다.(386ms 소요)

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        ans = []
        first_index = 0
        last_index = 0
        for i, ch in enumerate(s):
            # last_index 갱신
            for j in range(i + 1, len(s)):
                if s[j] == ch:
                    last_index = max(last_index, j)

            # 끝나는 위치면
            if i == last_index:
                ans.append(last_index - first_index + 1)
                first_index = i + 1
                last_index = i + 1

        return ans

discussion을 보니 char별 최대 index를 저장할 때 max()를 이용하지 않고, 아래와 같이 작성도 가능했습니다.(어차피 딕셔너리에서 덮어씌우므로)

for i, c in enumerate(s):
	lastIndex[c] = i