leetcode
leetcode 1451 ~ 1500
最大重复子字符串

最大重复子字符串

难度:

标签:

题目描述

代码结果

运行时间: 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`的子字符串后选择继续拼接,而不是先拼接再检查?
这种选择是为了确保每次拼接前,`word`已经是`sequence`的子字符串,从而确保每次拼接后的字符串(如果仍然是子字符串)确实代表了一个有效的重复。如果先进行拼接再检查,可能会造成在`word`尚未成为`sequence`的子字符串时就已经进行了拼接,这将导致不必要的计算和可能的错误结果,因为拼接后的字符串可能根本不是子字符串,从而导致错误地增加重复次数。
🦆
在`while`循环中,如何确保`word+s`在长度上不会超过`sequence`的长度,以避免不必要的性能损耗?
在题解中,没有直接的检查来确保`word+s`的长度不会超过`sequence`的长度。这确实可能导致性能损耗,尤其是在`sequence`较短而`word`较长的情况下。一个改进方法是在每次拼接前检查新的`word`长度是否会超过`sequence`的长度。如果超过,则可以提前终止循环。这样可以减少不必要的字符串比较操作,从而优化性能。
🦆
在什么情况下,这种直接拼接并检查的方法最不有效?
这种方法在`word`长度相对于`sequence`非常短,并且`word`可以重复很多次的情况下最不有效。因为每次拼接和检查都涉及到整个`sequence`的遍历,当需要多次重复拼接时,这种方法的效率极低。此外,如果`word`是`sequence`的一个非常频繁重复的子串,但每次都只增加一个`word`长度,这将导致大量的重复检查和字符串操作。在这种情况下,更高效的算法可能是使用KMP算法或其他字符串匹配算法来更快地确定子字符串的位置和重复次数。

相关问题