How to Compute the Greatest Common Divisor of Strings?

  • 时间:2020-09-24 11:41:27
  • 分类:网络文摘
  • 阅读:87 次

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 <= str1.length <= 1000
  • 1 <= str2.length <= 1000
  • str1[i] and str2[i] are English uppercase letters.

GCD of Strings Algorithms

Let’s review the GCD algorithm for two integers, which can be illustrated in the following C++ algorithm.

1
2
3
4
int gcd(int a, int b) { 
   if (b == 0) return a; 
   return gcd(b, a % b);  
} 
int gcd(int a, int b) { 
   if (b == 0) return a; 
   return gcd(b, a % b);  
} 

A bit similar, we need to check the terminating conditions that we can get the GCD directly. Otherwise, we need to make the longer string shorter by taking off the other string from the start. Then, the problem becomes a smaller problem, which can be recursively solved.

The first version of the recursive GCD algorithm for two strings in C++ as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 == str2) {
            return str1;
        }
        if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) {
            return "";
        }        
        if (str1.size() > str2.size()) {
            str1 = str1.substr(str2.size());
        }
        if (str2.size() > str1.size()) {
            str2 = str2.substr(str1.size());
        }
        return gcdOfStrings(str1, str2);
    }
};
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 == str2) {
            return str1;
        }
        if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) {
            return "";
        }        
        if (str1.size() > str2.size()) {
            str1 = str1.substr(str2.size());
        }
        if (str2.size() > str1.size()) {
            str2 = str2.substr(str1.size());
        }
        return gcdOfStrings(str1, str2);
    }
};

We also notice that if both strings do not contain each other, we can rewrite the string.find using a simpler logic:

1
2
3
if (str1 + str2 != str2 + str1) {
    return "";
}
if (str1 + str2 != str2 + str1) {
    return "";
}

For example, “123” + “123ABC” != “123ABC” + “123” and “ABC” + “ABCABC” == “ABCABC” + “ABC”. As the above recursion can be optimised using tail-recursion techniques, which can be converted to iterative while-loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        while (true) {
            if (str1 + str2 != str2 + str1) {
                return "";
            }
            if (str1 == str2) {
                return str1;
            }
            if (str1.size() > str2.size()) {
                str1 = str1.substr(str2.size());
            }
            if (str2.size() > str1.size()) {
                str2 = str2.substr(str1.size());
            }
        }
        return ""; // make compiler happy
    }
};
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        while (true) {
            if (str1 + str2 != str2 + str1) {
                return "";
            }
            if (str1 == str2) {
                return str1;
            }
            if (str1.size() > str2.size()) {
                str1 = str1.substr(str2.size());
            }
            if (str2.size() > str1.size()) {
                str2 = str2.substr(str1.size());
            }
        }
        return ""; // make compiler happy
    }
};

The space complexity is O(1) constant, and the time complexity is O(M/N) where M is the length of the longer string and N is the shorter length e.g. “A”, and “AAAAAAA…”

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Read This Before You Buy a Premium WordPress Theme  5 Trust Indicators And How To Use Them To Grow Your Blog  How to Merge k Sorted Lists using Recursive Divide and Conquer A  The String ZigZag Conversion Algorithms  How Experts Make Your Website Successful?  Replace Elements with Greatest Element on Right Side using C++ s  Compute the Deepest Leaves Sum of a Binary Tree using BFS or DFS  Microbit Programming: Snake Game with Growing Body and Greedy St  How to Make a Simple Snake Game in Javascript?  Integration Tests Using PHPUnit to Ensure Your Website is Workin 
评论列表
添加评论