Sergei Golitsyn provides solutions to popular leetcode problems.
Aloha guys today we have a popular GDS problem:
Description
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one 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: ""
Solution
To solve it we need to understand, what we want to find. We need to find greatest common part of two words, and this part should divide word on 1-N the same paths.
For example: a = ABCABC
and b = ABC
can be divided on a = ABC ABC
and b = ABC
In the next example a = ABABAB
and b = ABAB
we cannot divide a on b because a = ABAB AB
and ABAB != AB
. That is why we should reduce divider.
We can do it iteratively, but what if we start with the rest of the longest string?
a = ABABAB
after divide a has two parts common ABAB
and rest AB
. Let's try to use rest. Now let's try to divide longest string on short one, a = AB
and b = ABAB
. b will be AB AB
. Hm, obviously that AB
is greatest common divisor. But how can we understand it? We need to dive bit deeper and again use rest of division. a = ""
and b = AB
. If one of the strings is empty, another one will be our result. Wisdom, right?
Code
public String gcdOfStrings2(String str1, String str2) {
int l1 = str1.length();
int l2 = str2.length();
// Swap the parameters when needed
if (l1 < l2){
return gcdOfStrings(str2, str1);
}
// Since we swap
if (l2 == 0){
return str1;
}
// Check if str1 starts with str2
if (!str1.startsWith(str2)) {
return "";
}
return gcdOfStrings(str1.substring(l2), str2);
}
Top comments (0)