LeetCode.1071-字元串最大公約數(Greatest Common Divisor of Strings)

這是小川的第391次更新，第421篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第253題（順位題号是1071）。對于字元串

S

和

T

，當且僅當

S = T + ... + T

（

T

與自身連接配接1次或更多次）時，我們說

"T除S"

。

傳回最大的字元串

X

，使得

X

除以

str1

，

X

str2

例如：

輸入：str1 ="ABCABC"，str2 ="ABC"

輸出："ABC"

輸入：str1 ="ABABAB"，str2 ="ABAB"

輸出："AB"

輸入：str1 ="LEET"，str2 ="CODE"

輸出：""

注意：

• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000

• str1[i]

  str2[i]

  是英文大寫字母。

02 第一種解法

題目的要求是找出兩個字元串

str1

、

str2

的最大公約數，即

str1

str2

中都存在一個子串，并且都由這個子串重複出現一次或多次組成。

那麼，什麼情況下這兩字元串沒有最大公約數？

兩者分别前後拼接，但是不相等，那麼肯定不存在最大公約數。例如示例中的

str1 ="ABCABC"

str2 ="ABC"

str1

拼接

str2

後變成

"ABCABCABC"

str2

str1

"ABCABCABC"

。而

str1 ="LEET"

str2 ="CODE"

str1

str2

"LEETCODE"

str2

str1

"CODELEET"

，兩者顯然不相等，肯定不存在公約數。

那怎麼找到他們的最大公約數呢？

思路：借助字元串拆分。用不同的子串分别對

str1

str2

進行拆分，通過

String

的

split

方法實作，如果拆分後的字元串數組中沒剩下任何元素，表明可以被該子串整除。找到兩字元串中長度較小的，作為循環次數上限，從後往前依次截取子串，将截取出來的子串用來拆分

str1

str2

，如果拆分後得到的數組長度為0，則此子串就是最大公約數。

public String gcdOfStrings(String str1, String str2) {
    if (!(str1+str2).equals(str2+str1)) {
        return "";
    }
    int n = Math.min(str1.length(), str2.length());
    for (int i=n; i>=1; i--) {
        String temp = str2.substring(0, i);
        if (str2.split(temp).length == 0 && 
                str1.split(temp).length == 0) {
            return temp;
        }
    }
    return "";
}
           

03 第二種解法

和第一種解法思路類似，依舊是借助字元串的特性，使用替換來驗證最大公約數，通過

String

replaceAll

方法實作。

public String gcdOfStrings2(String str1, String str2) {
    if (!(str1+str2).equals(str2+str1)) {
        return "";
    }
    int n = Math.min(str1.length(), str2.length());
    for (int i=n; i>=1; i--) {
        if (n%i != 0) {
            continue;
        }
        String temp = str2.substring(0, i);
        if(str1.replaceAll(temp,"").equals("") && 
                str2.replaceAll(temp,"").equals("")) {
            return temp;
        }
    }
    return "";
}
           

04 第三種解法

我們還可以從數學角度來思考這個問題。

思路：将兩個字元串的長度看做求最大公約數的兩個整數，單獨寫一個求兩個數最大公約數的算法，算出最大公約數後，取兩字元串中長度較小的，截取子串，子串的長度就是前一步算出的最大公約數，該子串也就是我們最後要傳回的兩字元串的最大公約數。

public String gcdOfStrings3(String str1, String str2) {
    if (!(str1+str2).equals(str2+str1)) {
        return "";
    }
    int len = str1.length();
    int len2 = str2.length();
    int gcd = GCD(len, len2);
    if (len < len2) {
        return str1.substring(0, gcd);
    }
    return str2.substring(0, gcd);
}


public int GCD(int a, int b) {
    if (b == 0) {
        return a;
    }
    return a % b == 0 ? b : GCD(b, a % b);
}
           

05 第四種解法

我們還可以将第三種解法中用到的求最大公約數的遞歸方法，和字元串操作整合在一起。

找到兩個字元串中長度較大的那個，如果長度大的字元串包含較小長度字元串的所有字元，就用長度較小的字元串對較大中的子串進行替換，直到有一方為空串為止。

public String gcdOfStrings4(String str1, String str2) {
    if (str1.length() < str2.length()) {
        return gcdOfStrings4(str2, str1);
    }
    if (str2.isEmpty()) {
        return str1;
    }
    if (!str1.contains(str2)) {
        return "";
    }
    str1 = str1.replace(str2, "");
    return gcdOfStrings4(str2, str1);
}
           

06 小結

算法專題目前已連續日更超過七個月，算法題文章259+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！