1593. Split a String Into the Max Number of Unique Substrings
给一个字串s
把这个字串分成数个独立的子字串
且每个子字串不重复
请问最多可以分成几个子字串?
思路:
看到题目限制s最多就16个字符
那就用backtracking + hash table
hash table用来记录目前出现过的子字串
用递回如果s[:i+1]的子字串重复就跳过
不重复的话就把s[:i+1]记录在hash table后接着从s[i+1:]开始检查
一直到该次递回的s长度为0，就去看hash table有几个子字串
当检查完记得把s[:i+1]从hash table删掉
这样就可以得到答案了
golang code :
func maxUniqueSplit(s string) int {
if len(s) == 1 {
return 1
}
ans := 0
backtracking(&ans, s, make(map[string]struct{}))
return ans
}
func backtracking(ans *int, s string, rec map[string]struct{}) {
if len(s) == 0 {
*ans = max(*ans, len(rec))
return
}
for i := 0; i < len(s); i++ {
if _, ok := rec[s[:i+1]]; !ok {
rec[s[:i+1]] = struct{}{}
backtracking(ans, s[i+1:], rec)
delete(rec, s[:i+1])
}
}
}