重复的子字符串
难度:
标签:
题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
代码结果
运行时间: 25 ms, 内存: 16.1 MB
/*
* 题目思路：
* 同样的思路，我们使用 Java Stream API 实现此功能。
* 我们将 s 和自身拼接，然后移除第一个和最后一个字符，
* 再检查原字符串 s 是否出现在新字符串中。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean repeatedSubstringPattern(String s) {
String new_s = s + s;
// 使用 IntStream 查找是否存在 s
return IntStream.range(1, new_s.length() - 1)
.anyMatch(i -> new_s.substring(i, i + s.length()).equals(s));
}
}解释
方法:
这个题解的思路是，如果字符串 s 可以由一个子串重复多次构成，那么将 s 和自身拼接成一个新字符串 doubled_str，并去掉 doubled_str 的首尾字符得到 sliced_str，那么原字符串 s 一定会作为子串出现在 sliced_str 中。反之，如果 s 不能由一个子串重复多次构成，那么 s 就不会出现在 sliced_str 中。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中提到，通过拼接字符串并去掉首尾字符来检测重复子串。这种方法为什么能准确判断出字符串是否可以由其子串重复构成？
▷🦆
题解中生成了一个新的字符串 doubled_str 并从中去掉首尾字符得到 sliced_str，这种操作是否可能导致原始字符串 s 的某些重复模式在 sliced_str 中丢失？
▷🦆
针对非常短的字符串，比如长度为1或2的字符串，这种方法是否仍然有效？如果 s = 'a' 或 s = 'aa'，结果会是怎样？
▷🦆
在判断 s 是否出现在 sliced_str 中时，是否考虑了所有可能的出现位置，还是只检查了某一特定的位置？
▷相关问题
找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
重复叠加字符串匹配
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
示例 1：
输入：a = "abcd", b = "cdabcdab" 输出：3 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2：
输入：a = "a", b = "aa" 输出：2
示例 3：
输入：a = "a", b = "a" 输出：1
示例 4：
输入：a = "abc", b = "wxyz" 输出：-1
提示：
1 <= a.length <= 1041 <= b.length <= 104a和b由小写英文字母组成