686. Repeated String Match

leetcode medium

#csharp#leetcode#medium#string#tree

Task

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"

Output: 3

Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

C# solution

matched/original

public class Solution {
    public int RepeatedStringMatch(string A, string B) {
        int q = 1;
        var S = new StringBuilder(A);
        while (S.Length < B.Length) {
            S.Append(A);
            q++;
        }
        if (S.ToString().Contains(B)) return q;
        if (S.Append(A).ToString().Contains(B)) return q + 1;
        return -1;
    }
}

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 int RepeatedStringMatch(string A, string B) {
        int q = 1;
        var S = new StringBuilder(A);
        while (S.size() < B.size()) {
            S.Append(A);
            q++;
        }
        if (S.ToString().Contains(B)) return q;
        if (S.Append(A).ToString().Contains(B)) return q + 1;
        return -1;
    }
}

Java solution

matched/original

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int q = 1;
        StringBuilder S = new StringBuilder(A);
        while (S.length() < B.length()) {
            S.append(A);
            q++;
        }
        if (S.indexOf(B) >= 0) return q;
        if (S.append(A).indexOf(B) >= 0) return q + 1;
        return -1;
    }
}

JavaScript solution

matched/original

class Solution {
    repeatedStringMatch(A, B) {
        let q = 1
        let S = A
        while (S.length < B.length) {
            S += A
            q++
        }
        if (S.includes(B)) return q
        if ((S + A).includes(B)) return q + 1
        return -1
    }
}

Python solution

matched/original

class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        q = 1
        S = A
        while len(S) < len(B):
            S += A
            q += 1
        if B in S:
            return q
        if B in S + A:
            return q + 1
        return -1

Go solution

matched/original

package main

import (
    "strings"
)

func repeatedStringMatch(A string, B string) int {
    q := 1
    S := A
    for len(S) < len(B) {
        S += A
        q++
    }
    if strings.Contains(S, B) {
        return q
    }
    if strings.Contains(S+A, B) {
        return q + 1
    }
    return -1
}

Explanation

Algorithm

Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎