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. 파이썬으로 트라이 맛깔나게 구현하는 법 어디 없을까 싶다. 메모리가 너무 비효율적으로 드는 느낌.