LeetCode 1071: Greatest Common Divisor of Strings Solution
Master LeetCode problem 1071 (Greatest Common Divisor of Strings), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
Problem Explanation
Explanation:
To find the largest string that divides both str1 and str2, we need to check all possible common divisors of the two strings. We can do this by checking the length of the strings and comparing their prefixes. If both strings share a common prefix and the length of the prefix is a divisor of both strings, then that prefix is a potential candidate for the largest common divisor.
We iterate through the possible lengths of common divisors starting from the length of the shorter string. For each length, we check if the prefix of that length is a common divisor for both strings. If it is, we check if repeating that prefix would result in the original strings. If so, we have found the largest common divisor.
:
Solution Code
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
int gcdLength = gcd(str1.length(), str2.length());
return str1.substring(0, gcdLength);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1071 (Greatest Common Divisor of Strings)?
This page provides optimized solutions for LeetCode problem 1071 (Greatest Common Divisor of Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1071 (Greatest Common Divisor of Strings)?
The time complexity for LeetCode 1071 (Greatest Common Divisor of Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1071 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1071 in Java, C++, or Python.