1071. Greatest Common Divisor of Strings

\1071. Greatest Common Divisor of Strings

Easy

30985Share

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: ""

solution 递归求解

class Solution {
    public String gcdOfStrings(String str1, String str2) {
       if(str1.equals(str2)) return str1;
        else if(str1.length() > str2.length()) {
            String sub = str1.substring(str2.length());
            return gcdOfStrings(sub, str2);
        }
        else if(str1.length() < str2.length()){
            String sub2 = str2.substring(str1.length());
            return gcdOfStrings(str1, sub2);
        }
        else return "";
        
    }
}

solution2 辗转相除法

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1+str2).equals(str2+str1))  
            return "";

            int gcdVal = gcd(str1.length() , str2.length());
            return str2.substring(0, gcdVal);
        }

        public static int gcd(int p, int q) {
            if (q == 0) 
                return p;
            else 
                return gcd(q, p % q);

        }
}