Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729516562.A.39F.html
推 dont: 大師