LeetCode September Challenge(Day-3)

leetcode

Topic — Repeated Substring Pattern

Q. Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Logic:

Specifically for me, I learned and understood the concept of Knuth–Morris–Pratt algorithm(KMP algorithm) before going to solve the above question.

This above algorithm works for string searching for some regular pattern. After understanding the concept, it was easy to solve the above question.

Just add the whole string twice and cut the head and tail from the new string. And if we are able to find the existing/previous string, then we can return True, otherwise False.
Doubt? Let’s see the below code.

One line solution in Python:

code

leetcode

Happy Coding!!!

Here is the leetcode link:
https://leetcode.com/explore/challenge/card/september-leetcoding-challenge/554/week-1-september-1st-september-7th/3447/

Please feel free to comment, if you have any problem or doubt.

Thank You!!!
Never settle and always Hustle!!!
☺
-Gareeb CODER

(Thanks for your time and do encourage me to write more by clapping.)