前往
大廳
主題

LeetCode - 1668. Maximum Repeating Substring 解題心得

Not In My Back Yard | 2023-04-07 12:00:08 | 巴幣 100 | 人氣 192

題目連結:


題目意譯:
對於一個字串 sequence,一字串 word 如果 word 串接原本的自己 k 次之後是 sequence 的一個子字串,則 word 為 k-重複。word 的最大 k-重複值為最大的 k 值滿足 word 為對於 sequence 是 k-重複的。如果 word 不是 sequence 的一個子字串,word 的最大 k-重複值為 0。

給定字串 sequence 和 word,回傳 word 對於 sequence 的最大 k-重複之值。

限制:
1 ≦ sequence.length ≦ 100
1 ≦ word.length ≦ 100
sequence 和 word 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: sequence = "ababc", word = "ab"
輸出: 2
解釋: "abab" 為 "ababc" 的一個子字串。

範例 2:
輸入: sequence = "ababc", word = "ba"
輸出: 1
解釋: "ba" 為 "ababc" 的一個子字串。"baba" 不為 "ababc" 的一個子字串。

範例 3:
輸入: sequence = "ababc", word = "ac"
輸出: 0
解釋: "ac" 不為 "ababc" 的一個子字串。


解題思維:
直接窮舉出以下字串:
word
word + word
word + word + word
……
然後對於每個字串去找是否是 sequence 的一個子字串。如果是就窮舉下一個字串;反之,我們窮舉出多少字串(不含當前窮舉的這個不是 sequence 的子字串之字串)即為所求之最大 k-重複之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作