1071. Greatest Common Divisor of Strings (使用C語言解題)

1071. Greatest Common Divisor of Strings

Solved

Easy

Topics

Companies

Hint

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + 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: ""

 

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

google 翻譯：

對於兩個字串 s 和 t，當且僅當 s = t + t + t + ... + t + t（即 t 與其自身連接一次或多次）時，我們才說「t 除 s」。
給定兩個字串 str1 和 str2，傳回使 x 整除 str1 和 str2 的最大字串 x。

想法一：

一開始覺得，這真是的簡單層級的嗎？還是是我誤會題目，想太多了？
因為我覺得 str1 = "ABABABAB"，str2 = "ABAB"，回傳值應該是 "AB"。
所以對解法沒什麼想法，就先去參考了大神的解法...

把 str1 + str2 和 str2 + str1 兩個串接過的字串相比較。
如果相等就代表它們可以被除，這個真的好聰明。

之後再從較短的字串，找出重覆性的字串。
一個字元一個字元慢慢的串接，如果有和第一個字元相同的，
就可以用“短字串”和“用字元串接”的兩個字串做遞迴呼叫。

最後會遞迴到兩個字串都相同，就是我想要的答案了...

寫法一：

char* gcdOfStrings(char* str1, char* str2) {
    int len1 = (str1 ? strlen(str1) : 0);
    int len2 = (str2 ? strlen(str2) : 0);
    char *buf1 = malloc(len1 + len2 + 4);
    char *buf2 = malloc(len1 + len2 + 4);
    char start_char = '\0', *p = NULL;
    int i = 0;
    sprintf(buf1, "%s%s", str1, str2);
    sprintf(buf2, "%s%s", str2, str1);
    if(strcmp(buf1, buf2)) {
        free(buf1);
        free(buf2);
        return "";
    }
    strcpy(buf1, (len1 < len2) ? str1 : str2);

    memset(buf2, '\0', len1 + len2 + 4);
    while (buf1[i]) {
        if(start_char == '\0') {
            start_char = buf1[i];
        } else if(start_char == buf1[i] && (p = gcdOfStrings(buf1, buf2)) && strcmp(p, "")) {
            free(p);
            free(buf1);
            return buf2;
        }
        if(p) {
            if(strcmp(p, ""))
                free(p);
            p = NULL;
        }
        buf2[i] = buf1[i];
        i++;
    }
    free(buf1);
    return buf2;
}

結果一：

什麼！！題目不是我想的這樣！

它竟然希望回傳 "ABAB"，好吧！是我對題目想太多了...

想法二：

我頓時又沒什麼想法了，再去看看其他大神怎麼想的...
用字元判斷，相同就表示有機會被除，不相同就表示沒機會被除，可直接回傳""
一直判斷到任一方字元結束，如果兩字串同時結束，代表現在的字串就是答案，直接回傳字串即可。
否則就用短字串，和長字串剩下的字串用遞迴的方式再比一次。

寫法二：

char* gcdOfStrings(char* str1, char* str2) {
    int pointer = 0;
    while (str1[pointer] != '\0' && str2[pointer] != '\0') {
        if(str1[pointer] == str2[pointer]) {
            pointer++;
        }  else {
            return ""; // 任一個字元不相同就表示沒機會被除，可直接回傳""
        }
    }
    if (str1[pointer] == '\0' && str2[pointer] == '\0') {
        return str1; // 兩字串完全相等，回傳目前字串，即是答案
    } else {
        // 找短字串，和長字串剩下的字，用遞迴再比一次
        if (str1[pointer] == '\0') {
            return gcdOfStrings(str1, str2 + pointer);
        }  else{
            return gcdOfStrings(str1 + pointer, str2);
        }
    }
}

結果二：

毫無懸念的，速度滿百，記憶體卻普普，可以了，我接受~