????前言
???? 算法题 ????
???? 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程????
???? 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
???? 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧????！
???? 今天是力扣算法题持续打卡第77天????！
???? 算法题 ????
????原题样例：重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。
给定的字符串只含有小写英文字母，并且长度不超过10000。
示例1:
输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
示例2:
输入: "aba" 输出: False
示例3:
输入: "abcabcabcabc" 输出: True 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。) • 1 • 2 • 3 • 4 • 5
提示：
1 <= num1.length, num2.length <= 104
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
????C#方法：排序遍历
使用给定的字符串去构造 next 数组,内部是DP 的实现 --> next 数组,索引和值存储的都是字符串中字符的数组下标
判断 next 数组是否满足一个特定的条件
代码：
public class Solution { public bool RepeatedSubstringPattern(string s) { var nextArray = GetKMPNextArray(s); var tailIndex = s.Length - 1; return nextArray[tailIndex] != -1 && s.Length % (tailIndex - nextArray[tailIndex]) == 0; } private int[] GetKMPNextArray(string s) { var forReturn = Enumerable.Repeat(-1, s.Length).ToArray(); for (var i = 1; i < s.Length; i++) { var j = forReturn[i - 1]; while (j >= 0 && s[j + 1] != s[i]) j = forReturn[j]; if (s[j + 1] == s[i]) forReturn[i] = j + 1; } return forReturn; } }
执行结果
通过 执行用时：96 ms，在所有 Java 提交中击败了46.50%的用户 内存消耗：46.4 MB，在所有 Java 提交中击败了38.90%的用户
????Java 方法：计数
思路解析
代码：
class Solution { public boolean repeatedSubstringPattern(String s) { int n = s.length(); for (int i = 1; i * 2 <= n; ++i) { if (n % i == 0) { boolean match = true; for (int j = i; j < n; ++j) { if (s.charAt(j) != s.charAt(j - i)) { match = false; break; } } if (match) { return true; } } } return false; } }
执行结果
通过 执行用时：9 ms，在所有 Java 提交中击败了77.76%的用户 内存消耗：38.7 MB，在所有 Java 提交中击败了80.40%的用户
复杂度分析
时间复杂度：O( n^2) 空间复杂度：O(1)
????总结
- 今天是力扣算法题打卡的第七十七天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们