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])
}
}
}