Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

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

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

Пример:

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

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

class Solution {
    function valid($str1, $str2, $k) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        if ($len1 % $k > 0 || $len2 % $k > 0) {
            return false;
        } else {
            $base = substr($str1, 0, $k);
            $n1 = intval($len1 / $k);
            $n2 = intval($len2 / $k);
            return $str1 == $this->joinWords($base, $n1) && $str2 == $this->joinWords($base, $n2);
        }
    }

    function joinWords($str, $k) {
        $ans = "";
        for ($i = 0; $i < $k; ++$i) {
            $ans .= $str;
        }
        return $ans;
    }

    function gcdOfStrings($str1, $str2) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        for ($i = min($len1, $len2); $i >= 1; --$i) {
            if ($this->valid($str1, $str2, $i)) {
                return substr($str1, 0, $i);
            }
        }
        return "";
    }
}

Ставь 👍 и забирай 📚 Базу знаний