1071.Greatest Common Divisor of Strings

Tags: Easy String

Links: https://leetcode.com/problems/greatest-common-divisor-of-strings/

---

For strings S and T, we say "T divides S" if and only if S = T + ... + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

Example 1:

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

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Note:

1. 1 <= str1.length <= 1000
2. 1 <= str2.length <= 1000
3. str1[i] and str2[i] are English uppercase letters.

---

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = str1.size(), n = str2.size();
        //寻找两个字符串的最长公共前缀
        int len = 0;
        for (int i = 0; i < n && i < m; ++i) {
            if (str1[i] == str2[i]) {
                ++len;
            }
            else break;
        }
        if (!len) return "";

        string prefix = str1.substr(0, len);
        for (int i = len - 1; i >= 0; --i) {
            string tmp = prefix.substr(0, i + 1);
            if (check(tmp, str1) && check(tmp, str2)) {
                return tmp;
            }
        }

        return "";
    }

    bool check(const string & tmp, const string s)
    {
        int m = tmp.size(), n = s.size();
        if (n % m == 0) {
            string res;
            int times = n / m;
            for (int i = 0; i < times; ++i) res += tmp;
            return res == s;
        } 
        return false;
    }
};

---

字符串中的GCD方法：

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (str1.size() < str2.size()) std::swap(str1, str2);
        int m = str1.size(), n = str2.size();
        if (n == 0) return str1;

        for (int i = 0; i < n; ++i) {
            if (str1[i] != str2[i])
                return "";
        }
        return gcdOfStrings(str1.substr(n, m - n), str2);
    }   
};