提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【算法千题案例】每日LeetCode打卡——77.重复的子字符串

算法
2023-03-14 22:53:22 时间

原题样例：重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。

给定的字符串只含有小写英文字母，并且长度不超过10000。

示例1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例2:

输入: "aba"

输出: False

示例3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

提示：

  • 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 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦，明天再见！

相关文章