1593. Split a String Into the Max Number of Unique Substrings

Problem : https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:08:17

 

---

 

문제 설명

 

 

문자열 s가 주어졌을때, 주어진 문자열을 분할하여 얻을 수 있는 유일 부분 문자열의 가장 큰 개수를 반환하라.

 

문자열 s는 임의의 공백이 아닌 부분문자열 리스트로 분할할 수 있고, 이 부분문자열을 이었을 때 원본 문자열이 된다. 그러나, 모든 부분문자열이 유일하도록 분할이 반드시 이루어져야 한다.

 

부분 문자열은 문자열 내부에 존재하는 연속적인 문자들로 정의된다.

---

 

풀이

 

DFS로 풀어보자.

 

현재 i번째 문자열부터 탐색을 진행한다고 할때, 전체 문자열까지 부분 문자열 후보를 차례대로 얻어낼 수 있을 것이다. 이 중 기존에 방문했던 부분문자열이 아닌 경우에, 그 다음 인덱스를 재귀적으로 방문해 볼 수 있다. 마지막 인덱스까지 방문할 수 있었다면, 유일 부분 문자열들로 전체를 순회한 것이 되므로 정답 후보군이 된다. 이러한 정답 후보군 중 가장 큰 값을 출력하면 되겠다.

 

 

풀이 코드

class Solution:
    visit = set()
    def dfs(self, s, idx) :
        if idx == len(s) :
            return len(self.visit)

        res = 0
        tmp = ''
        for i in range(idx, len(s)) :
            tmp += s[i]
            if tmp not in self.visit :
                self.visit.add(tmp)
                res = max(res, self.dfs(s, i+1))
                self.visit.discard(tmp)
        return res


    def maxUniqueSplit(self, s: str) -> int:
        self.visit = set()
        return self.dfs(s, 0)