最大重复子字符串
难度:
标签:
题目描述
代码结果
运行时间: 21 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用流生成可能的重复次数列表。
* 2. 遍历这些可能的重复次数,并检查包含k个word的字符串是否为sequence的子串。
* 3. 返回最大重复次数。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxRepeating(String sequence, String word) {
return IntStream.iterate(1, i -> i + 1)
.mapToObj(k -> word.repeat(k))
.takeWhile(repeatedWord -> repeatedWord.length() <= sequence.length())
.filter(sequence::contains)
.mapToInt(repeatedWord -> repeatedWord.length() / word.length())
.max()
.orElse(0);
}
}
解释
方法:
该题解采用了简单直观的方法来解决问题。首先定义两个变量,s用于存储原始的word,res用于记录word重复的次数。通过一个循环,每次循环将word与s进行拼接以形成更长的字符串,并检查这个新形成的字符串是否为sequence的子字符串。如果是,res增加1;如果不是,则终止循环。最终返回的res即为最大重复值k。
时间复杂度:
O(n^2/m)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在检查`word`是否是`sequence`的子字符串后选择继续拼接,而不是先拼接再检查?
▷🦆
在`while`循环中,如何确保`word+s`在长度上不会超过`sequence`的长度,以避免不必要的性能损耗?
▷🦆
在什么情况下,这种直接拼接并检查的方法最不有效?
▷