1071. Greatest Common Divisor of Strings

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

Given two strings str1 and str2, return the largest string x such that x divides both str1 and 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: ""
Example 4:

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

Constraints:

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1 and str2 consist of English uppercase letters.

这题让求两个字符串的最大公约串。虽然是Easy题，但是一开始我想了好久，最后还是使用笨办法去解题了。

主要思路如下，首先我们挑出个短的那个字符串，然后对其进行切分，当然一开始是完整的，因为它能被公约，说明肯定被切分为整数部分了。

剩下的，就是看该部分能不能满足公约条件，并且判断能不能满足长串的公约条件，如此就可以求出最大公约串。

class GreatestCommonDivisorOfStrings : public Solution {
public:
    void Exec() {
        cout << "Case 1: " << gcdOfStrings("AAAAA",
"AA") << std::endl;
    }

    string gcdOfStrings(string str1, string str2) {
        string shortstr;
        string longstr;

        if (str1.size() > str2.size()) {
            shortstr = str2;
            longstr = str1;
        } else {
            shortstr = str1;
            longstr = str2;
        }

        for (int div = 1; shortstr.size() / div > 0; div++) {
            if (shortstr.size() % div != 0) {
                continue;
            }
            if (longstr.size() % (shortstr.size() / div) != 0) {
                continue;
            }

            int part = shortstr.size() / div;
            int index = 0;
            bool match = true;
            for (int i = 1; i < div; i++) {
                if (0 != memcmp(shortstr.c_str() + i * part, shortstr.c_str(), part)) {
                    match = false;
                    break;
                }
            }
            if (!match) {
                continue;
            }

            // Does the short string part divs long string ?
            match = true;
            for (int i = 0; i < longstr.size() / part; i++) {
                if (0 != memcmp(longstr.c_str() + i * part, shortstr.c_str(), part)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return shortstr.substr(0, part);
            }
        }
        return "";
    }
};