Solution for Greatest Common Divisor of Strings.

At first, I used a pretty brute-force approach, and the code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool check(string s, string ans) {
        int lens = s.size();
        int lenans = ans.size();
        if(lens % lenans) return false;
        for(int i = 0; i < lens/lenans; i++) {
            int start = i * lenans;
            if(s.substr(start, lenans) != ans)
                return false;
        }
        return true;
    }

    string gcdOfStrings(string str1, string str2) {
        string ans = "";
        
        // ensuring that str1 is always the shorter one
        if (str1.size() > str2.size()) {
            string tmp = str1;
            str1 = str2;
            str2 = tmp;
        }

        for(int i = 1; i <= str1.size(); i++) {
            string tmp = str1.substr(0, i);
            if(check(str1, tmp) && check(str2, tmp)) {
                ans = tmp;
            }
        }
        
        return ans;
    }
};

This approach performed poorly in terms of both rumtime and memory usage. Subsequently, I found a rather tricky approach.

TODO…

1

Reference