[Leetcode 1071] 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.

解题思路

这道题可以用递归来求解，和求两个数的最大公约数类似。
首先，str1和str2(假设str1.size() >= str2.size())有最大公约数的必要条件是str1的前缀等于str2。
原因如下，假设最大公约字符串为divisor_str，那么str1 = x * divisor_str，str2 = y * divisor_str (x, y为正整数，且x >= y)，
所以str1的前y个divisor_str就等于str2。
其次，我们希望求两个字符串的最大公约字符串，就等于求两个字符串之差和其中一个字符串的最大公约字符串。还是用上述例子：
str1与str2的最大公约数，也是str1 - str2 = (y - x) * divisor_str 与 str2 = y * divisor_str的最大公约数。
当y = x时，str2本身即为str1和str2的最大公约数。

示例代码 (cpp)

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // Puts longer string first
        if (str1.size() < str2.size()) {
            return gcdOfStrings(str2, str1);
        }
        if (str2.empty()) {
            return str1;
        }
        // If str1 is not starts with str2, they don't have common divisor.
        if (str1.substr(0, str2.size()) != str2) {
            return "";
        }
        return gcdOfStrings(str1.substr(str2.size()), str2);
    }
};

示例代码 (java)

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (str1.length() < str2.length()) { // make sure str1 is not shorter than str2.
            return gcdOfStrings(str2, str1); 
        }else if (!str1.startsWith(str2)) { // shorter string is not common prefix.
            return ""; 
        }else if (str2.isEmpty()) { // gcd string found.
            return str1;
        }else { // cut off the common prefix part of str1.
            return gcdOfStrings(str1.substring(str2.length()), str2); 
        }
    }
}

示例代码 (python)

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not str1 or not str2:
            return str1 if str1 else str2
        elif len(str1) < len(str2):
            return self.gcdOfStrings(str2, str1)
        elif str1[: len(str2)] == str2:
            return self.gcdOfStrings(str1[len(str2) :], str2)
        else:
            return ''

复杂度分析

时间复杂度: O(M + N), M和N为str1和str2的长度, 主要是str1.substr(0, str2.size()) != str2这一判断会遍历一遍每一个字符
空间复杂度: O(1), 栈的最大深度为O(max(M, N)), 因为最坏的情况len(str2) = 1，那么递归深度就是len(str1), 即O(M).

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！