Greatest Common Divisor of Strings

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

Solution

Solution 1:

Code:

public String gcdOfStrings(String str1, String str2) {
  
  int len1 = str1.length, len2 = str2.length();
  int maxLen = Math.min(str1.length(), str2.length());
  String res = "";

  for (int len = 1; len <= maxLen; len++) {
    if (len1 % len != 0 || len2 % len != 0) continue;

    String sub = str1.substring(0, len);

    if (str1.replaceAll(sub, "").isEmpty() && str2.replaceAll(sub, "").isEmpty())
      res = sub;
  }

  return res;
}

Solution 2: Using gcd algorithm, more efficient

Click here to know more about gcd.

Code:

public String gcdOfStrings(String str1, String str2) {
  if (str1.length() < str2.length())
    return gcdOfStrings(str2, str1);

  if (str2.equals(""))
    return str1;

  if (!str1.startsWith(str2))
    return "";

  return gcdOfStrings(str2, str1.substring(str2.length()));
}

Some Methods in Class String

• replaceAll(String regex, String replacement):Replaces each substring of this string that matches the given regular expression with the given replacement, replaceFirst(String regex, String replacement).
• replace(char oldChar, char newChar), replace(CharDequence target, CharSequence replacement)
• startsWith(String prefix): Tests if this string starts with the specified prefix.
• endsWith(String suffix): Tests if this string ends with the specified suffix.
• charAt(index)
• compareTo(String anotherString: Compares two strings lexicographically.
• indexOf(int ch), indexOf(int ch, int fromIndex), indexOf(String str), indexOf(String str, int fromIndex), lastIndexOf(int ch),……
• isEmpty(): Returns true if, and only if, length() is 0.
• split(String regex): Splits this string around matches of the given regular expression, returns String[].
• substring(int beginIndex), substring(int beginIndex, int endIndex)
• toCharArray()
• toLowerCase(), toUpperCase()
• trim()
• valueOf(char[] data), valueOf(double d), valueOf(float f), valueOf(int i), valueOf(long l): returns static String.