By Long Luo
今天 LeetCode CN 的每日一题是 1668. 最大重复子字符串 ,本文是该题的题解,同时发表在 这里 。
思路
这道题有好几个方法:
- API:使用 String API contains(CharSequence s) 来判断 sequence 中是否存在拼接的 N 个 word 字符串;
- KMP: 使用 KMP 算法判断 sequence 中是否存在拼接的 N 个 word 字符串;
- 暴力:判断是否存在拼接的 N 个 word ,虽然很简单,但代码要写的优雅简洁有难度。
API 方法最简单,但 KMP 算法比较复杂。看了一些题解里的暴力解法,大多数人的暴力解法写的太复杂。我自己写该题暴力解法也写了 3 个版本,前 2 个版本也很复杂,逐渐优化为目前的简洁优雅版本。
暴力解法使用 2 个循环,第 1 个循环,遍历 sequence 中的每个字符,判断是否和 word.charAt(0) 相同,相同的话的进入下一步;
使用一个索引 j ,0≤j≤len−i ,而这里 word 字符索引可以使用 jmodwLen 来获取,这是暴力解法中最优雅的地方。如果遇到不相同的字符,跳出循环。
最后更新最大重复子字符串,就是 ans 和 j/wLen 的更大值。
中间其实还可以剪枝,但由于数据量比较小,就不加了。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public int maxRepeating(String sequence, String word) { int sLen = sequence.length(); int wLen = word.length();
int ans = 0;
for (int i = 0; i < sLen; i++) { if (sequence.charAt(i) != word.charAt(0)) { continue; } int j = 0; while (i + j < sLen && sequence.charAt(i + j) == word.charAt(j % wLen)) { j++; }
ans = Math.max(ans, j / wLen); }
return ans; } }
|
复杂度分析
- 时间复杂度:O(n2) ,其中 n 是字符串 sequence 长度,存在 2 个循环,所以总时间复杂度为 O(n2) 。
- 空间复杂度:O(1) 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗