1.题目
给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的重复值为 k 。单词 word 的最大重复值是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串,那么重复值 k 为 0 。
给你一个字符串 sequence 和 word ,请你返回最大重复值 k 。
示例 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” 的子字符串。
提示: 1 <= sequence.length <= 100 1 <= word.length <= 100 sequence 和 word 都只包含小写英文字母。
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/maximum-repeating-substring
2.思路
(1)暴力穷举法 重复拼接 word,然后使用 contains() 方法来判断字符串 sequence 中是否包含拼接后的子串,并且用 k 来记录最大拼接次数。
(2)简单枚举 & 动态规划 思路参考本题官方题解。
3.代码实现(Java)
class Solution {
public int maxRepeating(String sequence, String word) {
int k = 0;
if (sequence.length() < word.length()) {
return k;
}
String s = word;
while (sequence.contains(s)) {
k++;
s += word;
}
return k;
}
}
class Solution {
public int maxRepeating(String sequence, String word) {
int k = 0;
int seqLen = sequence.length();
int wordLen = word.length();
if (seqLen < wordLen) {
return k;
}
int[] dp = new int[seqLen];
for (int i = wordLen - 1; i < seqLen; i++) {
boolean valid = true;
for (int j = 0; j < wordLen; j++) {
if (sequence.charAt(i - wordLen + 1 + j) != word.charAt(j)) {
valid = false;
break;
}
}
if (valid) {
dp[i] = (i == wordLen - 1 ? 0 : dp[i - wordLen]) + 1;
}
}
return Arrays.stream(dp).max().getAsInt();
}
}
|