“This is the 17th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 77th day 🎈!
🚀 Algorithm 🚀

🌲 Duplicate substring

Given a non-empty string, determine whether it can be formed by repeating one of its substrings more than once.

The given string contains only lowercase English letters and cannot exceed 10000 characters.

Example 1:

Input:"abab"Output: True Explanation: Can be a substring"ab"Repeat the composition twice.Copy the code

Example 2:

Input:"aba"Output: FalseCopy the code

Example 3:

Input:"abcabcabcabc"Output: True Explanation: Can be a substring"abc"Repeat the composition four times. (Or substrings"abcabc"Repeat the composition twice.Copy the code

Tip:

  • 1 <= num1.length, num2.length <= 104
  • Both num1 and num2 contain only the numbers 0-9
  • Neither num1 nor num2 contain any leading zeros

🌻C# method: sort traversal

Construct the next array using the given string, inside the DP implementation –> next array, index and value store the array subscripts of the characters in the string

Determines whether the next array satisfies a particular condition

Code:

public class Solution {
        public bool RepeatedSubstringPattern(string s)
        {
            var nextArray = GetKMPNextArray(s);
            var tailIndex = s.Length - 1;
            returnnextArray[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;
            }

            returnforReturn; }}Copy the code

The execution result

By execution time:96Ms, beat out all Java commits46.50% user memory consumption:46.4MB, beat out all Java commits38.90% of the userCopy the code

🌻Java methods: count

Thinking analytical

Code:

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; }}Copy the code

The execution result

By execution time:9Ms, beat out all Java commits77.76% user memory consumption:38.7MB, beat out all Java commits80.40% of the userCopy the code

Complexity analysis

Time complexity: O(n^2) Space complexity: O(1) 
Copy the code

💬 summary

  • Today is the seventy-seventh day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!