Re: [閒聊] 每日leetcode
1593. Split a String Into the Max Number of Unique Substrings
## 思路
backtracking
用set紀錄s[:i]的字串組合
如果s[i:j]是新的組合就加到set 檢查s[j:]
## Code
```python
class Solution:
def maxUniqueSplit(self, s: str) -> int:
n = len(s)
seen = set()
self.res = 1
def backtrack(i):
if i == n:
self.res = max(self.res, len(seen))
return
for j in range(i+1, n+1):
if s[i:j] in seen:
continue
seen.add(s[i:j])
backtrack(j)
seen.remove(s[i:j])
backtrack(0)
return self.res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729508301.A.0F3.html
※ 編輯: dont (94.156.205.10 臺灣), 10/21/2024 18:58:51
推
10/21 19:14,
1年前
, 1F
10/21 19:14, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1016 之 1553 篇)：