459. Repeated Substring Pattern

leetcode easy

#csharp#easy#leetcode#prefix-sum#string#tree

Task

Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.

Пример:

Input: heights = [2,1,5,6,2,3]

Output: 10

Explanation: The above is a histogram where width of each bar is 1.

The largest rectangle is shown in the red area, which has an area = 10 units.

C# solution

matched/original

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        int n = s.Length;
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                string pattern = "";
                string substr = s.Substring(0, i);
                for (int j = 0; j < n / i; j++) {
                    pattern += substr;
                }
                if (s == pattern) {
                    return true;
                }
            }
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool RepeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                string pattern = "";
                string substr = s.Substring(0, i);
                for (int j = 0; j < n / i; j++) {
                    pattern += substr;
                }
                if (s == pattern) {
                    return true;
                }
            }
        }
        return false;
    }
}

Java solution

matched/original

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                StringBuilder pattern = new StringBuilder();
                for (int j = 0; j < n / i; j++) {
                    pattern.append(s.substring(0, i));
                }
                if (s.equals(pattern.toString())) {
                    return true;
                }
            }
        }
        return false;
    }
}

JavaScript solution

matched/original

class Solution {
    repeatedSubstringPattern(s) {
        const n = s.length;
        for (let i = 1; i <= n / 2; i++) {
            if (n % i === 0) {
                let pattern = '';
                const substr = s.substring(0, i);
                for (let j = 0; j < n / i; j++) {
                    pattern += substr;
                }
                if (s === pattern) {
                    return true;
                }
            }
        }
        return false;
    }
}

Python solution

matched/original

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                pattern = s[:i] * (n // i)
                if s == pattern:
                    return True
        return False

Go solution

matched/original

package main

import "strings"

func repeatedSubstringPattern(s string) bool {
    n := len(s)
    for i := 1; i <= n/2; i++ {
        if n%i == 0 {
            pattern := strings.Repeat(s[:i], n/i)
            if s == pattern {
                return true
            }
        }
    }
    return false
}

Explanation

Algorithm

Создайте целочисленную переменную n, равную длине строки s.

Итерация по всем префиксным подстрокам длины i от 1 до n/2:

Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.

Если pattern равен s, вернуть true.

Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎