새소식

PS/LeetCode

2707. Extra Characters in a String

  • -

Problem : https://leetcode.com/problems/extra-characters-in-a-string

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:22:04

 


 

문제 설명

 

 

더보기

0-인덱스의 문자열 s와 단어들의 사전인 dictionary가 주어진다. s를 하나 이상의 겹치지 않는 부분 문자열로 나누며, 부분 문자열은 dictionary 내에 존재해야 한다. 이 부분 문자열 어디에도 속하지 않는 잉여 문자들이 존재할 수 있다.

 

s를 최적으로 쪼갠다고 가정할 때, 남는 잉여 문자들의 최소 개수를 반환하라.


 

풀이

 

순수 DP로도 풀 수 있다. 조금 비효율적이겠지만.

현재 idx를 기준으로

  • 현재 idx의 문자가 잉여 문자임을 가정한다. 그렇다면 dp[idx+1] = min(dp[idx+1], dp[idx]+1) 이 될 것이다.
  • dictionary의 하나의 문자가 정확히 idx부터 시작되는 부분 문자열이라고 하자. 그 문자열의 길이가 d라고 할 때, dp[d+1] = min(dp[d+1], dp[idx]) 가 될 것이다.

각각의 idx마다 딕셔너리의 모든 문자열을 검사하여, 그 문자열이 s의 부분문자열인지 확인하면 된다. 참 쉽죠? 이 경우, 최대 시간복잡도는 O(S * D * L)이 될 것이다(문자열의 길이 * 딕셔너리의 크기 * 딕셔너리 평균 단어들의 길이). 각각이 최대 50이므로 O(50^3)복잡도가 된다.

 

여기에 우리는 트라이 역시 써 볼 수 있을 것이다.

  • 딕셔너리의 단어들을 트라이로 만든다.
  • 현재 idx의 문자가 잉여 문자임을 가정한다. 그렇다면 dp[idx+1] = min(dp[idx+1], dp[idx]+1) 이 될 것이다. (여기까지는 동일하다)
  • 이제부터 idx 문자열부터 차례대로 트라이와 비교해볼 것이다.
    • 만약 트라이의 현재 문자열과 idx 문자열이 일차히지 않으면, 더 탐색할 필요가 없다(해당 딕셔너리에는 더 이상 부분문자열 조건을 만족하는 단어가 존재하지 않는다)
    • 만약 트라이의 현재 문자열을 방문했을때, 그 문자열이 어떤 딕셔너리의 끝 단어라면 - 그 단어는 s의 부분 문자열이 될 수 있음을 의미한다. 이 때의 idx = d라고 둔다면 dp[d+1] = min(dp[d+1], dp[idx])가 될 것이다.
    • idx를 증가시켜, 트라이 탐색이 더 이상 불가능할 때까지 반복한다.

 

이 경우는 현재 idx를 기준으로 모든 딕셔너리를 방문하는 대신, 최대 하나의 최장 단어만을 방문하게 될 것이다.

트라이를 생성하는 데 O(D * L), 트라이를 방문하는 데 O(S*L)이 될 것이므로 총 시간복잡도는 O(50^2) 정도가 될 것으로 예측해볼 수 있겠다.

 

 

풀이 코드

class Solution: trie = {} dp = [] def makeTrie(self, d: str) : cur = self.trie for i in range(len(d)) : if d[i] not in cur : cur[d[i]] = [False, dict()] if i == len(d) - 1 : cur[d[i]][0] = True cur = cur[d[i]][1] def isSubMatched(self, s: str, i: int) : self.dp[i+1] = min(self.dp[i+1], self.dp[i]+1) cur = self.trie idx = i while idx < len(s) : if s[idx] not in cur : return if cur[s[idx]][0] : self.dp[idx+1] = min(self.dp[idx+1], self.dp[i]) cur = cur[s[idx]][1] idx += 1 def minExtraChar(self, s: str, dictionary: List[str]) -> int: MAX = len(s) self.trie = {} self.dp = [0] + [MAX+1]*MAX for d in dictionary : self.makeTrie(d) for i in range(MAX) : self.isSubMatched(s, i) return self.dp[-1]

 

P.S. 파이썬으로 트라이 맛깔나게 구현하는 법 어디 없을까 싶다. 메모리가 너무 비효율적으로 드는 느낌.

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.