1071. Greatest Common Divisor of Strings

leetcode easy

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

Task

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"

Output: "ABC"

C# solution

matched/original

public class Solution {
    public bool Valid(string str1, string str2, int k) {
        int len1 = str1.Length, len2 = str2.Length;
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string baseStr = str1.Substring(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == JoinWords(baseStr, n1) && str2 == JoinWords(baseStr, n2);
        }
    }
    public string JoinWords(string str, int k) {
        var sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            sb.Append(str);
        }
        return sb.ToString();
    }
    public string GcdOfStrings(string str1, string str2) {
        int len1 = str1.Length, len2 = str2.Length;
        for (int i = Math.Min(len1, len2); i >= 1; i--) {
            if (Valid(str1, str2, i)) {
                return str1.Substring(0, i);
            }
        }
        return "";
    }
}

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 Valid(string str1, string str2, int k) {
        int len1 = str1.size(), len2 = str2.size();
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string baseStr = str1.Substring(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == JoinWords(baseStr, n1) && str2 == JoinWords(baseStr, n2);
        }
    }
    public string JoinWords(string str, int k) {
        var sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            sb.Append(str);
        }
        return sb.ToString();
    }
    public string GcdOfStrings(string str1, string str2) {
        int len1 = str1.size(), len2 = str2.size();
        for (int i = min(len1, len2); i >= 1; i--) {
            if (Valid(str1, str2, i)) {
                return str1.Substring(0, i);
            }
        }
        return "";
    }
}

Java solution

matched/original

class Solution {
    fun valid(str1: String, str2: String, k: Int): Boolean {
        val len1 = str1.length
        val len2 = str2.length
        if (len1 % k > 0 || len2 % k > 0) {
            return false
        } else {
            val base = str1.substring(0, k)
            val n1 = len1 / k
            val n2 = len2 / k
            return str1 == base.repeat(n1) && str2 == base.repeat(n2)
        }
    }

    fun gcdOfStrings(str1: String, str2: String): String {
        val len1 = str1.length
        val len2 = str2.length
        for (i in minOf(len1, len2) downTo 1) {
            if (valid(str1, str2, i)) {
                return str1.substring(0, i)
            }
        }
        return ""
    }
}

JavaScript solution

matched/original

class Solution {
    valid(str1, str2, k) {
        let len1 = str1.length, len2 = str2.length;
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            let base = str1.slice(0, k);
            let n1 = Math.floor(len1 / k), n2 = Math.floor(len2 / k);
            return str1 === this.joinWords(base, n1) && str2 === this.joinWords(base, n2);
        }
    }
    
    joinWords(str, k) {
        let ans = '';
        for (let i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }

    gcdOfStrings(str1, str2) {
        let len1 = str1.length, len2 = str2.length;
        for (let i = Math.min(len1, len2); i >= 1; --i) {
            if (this.valid(str1, str2, i)) {
                return str1.slice(0, i);
            }
        }
        return "";
    }
}

Python solution

matched/original

class Solution:
    def valid(self, str1, str2, k):
        len1, len2 = len(str1), len(str2)
        if len1 % k > 0 or len2 % k > 0:
            return False
        else:
            base = str1[:k]
            n1, n2 = len1 // k, len2 // k
            return str1 == base * n1 and str2 == base * n2
    
    def gcdOfStrings(self, str1, str2):
        len1, len2 = len(str1), len(str2)
        for i in range(min(len1, len2), 0, -1):
            if self.valid(str1, str2, i):
                return str1[:i]
        return ""

Go solution

matched/original

func valid(str1, str2 string, k int) bool {
    len1, len2 := len(str1), len(str2)
    if len1 % k > 0 || len2 % k > 0 {
        return false
    } else {
        base := str1[:k]
        n1, n2 := len1 / k, len2 / k
        return str1 == joinWords(base, n1) && str2 == joinWords(base, n2)
    }
}

func joinWords(str string, k int) string {
    ans := ""
    for i := 0; i < k; i++ {
        ans += str
    }
    return ans
}

func gcdOfStrings(str1, str2 string) string {
    len1, len2 := len(str1), len(str2)
    for i := min(len1, len2); i >= 1; i-- {
        if valid(str1, str2, i) {
            return str1[:i]
        }
    }
    return ""
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎