leetcode_3_13

title: LeetCode 1071：字符串的最大公因子
tags: leetcode
categories: LeetCode

mathjax: true

题目描述

标准解答数学 $O(n)$

首先证明：如果str1+str2等于str2+str1，则一定存在符合条件的字符串X。

必要性：

$str1=X+X+…+X=nX,str2=X+X+…+X=mX$，则$str1+str2=(n+m)X=(m+n)X=str2+str1$

充分性（证明其逆否命题成立）：

将str1分为长度最小的相等的n份，str2分为m份，$str1=X_1+…+X_n,str2=Y_1+…+Y_m$，则$str1+str2=X_1+…+X_n+Y_1+…+Y_m$，$str2+str1=Y_1+…+Y_m+X_1+…+X_n$。若不存在符合条件的X，则$X_1 ≠ Y_1, …, Y_m ≠ X_n$，也即$str1+str2 ≠ str2+str1$，从而逆否命题成立，原命题也成立。

满足题意的X的长度的最大值即为gcd(str1.length(), str2.length())（gcd(n, m)个X相连接）

inline int gcd(int a, int b) {
    return b>0? gcd(b, a%b) : a;
}

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        return str1.substr(0, gcd((int)str1.length(), (int)str2.length()));
    }
};

字符串比较$O(n)$，gcd开销$O(logn)$，总和为$O(n)$。

个人解法 $O(\frac{n^2}{m}logn)$

利用gcd的思想写字符串的mod函数

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str2 == "") {
            return str1;
        }
        if (str1.length() >= str2.length()) {
            string smod = mod(str1, str2);
            if (smod == str1) { 
                return "";
            }
            return gcdOfStrings(str2, smod);
        }
        else {
            return gcdOfStrings(str2, str1);
        }
    }
    
    string mod(string str1, string str2) {
        if (str1.length() == str2.length()) {
            if (str1 == str2) {
                return "";
            }
            else {
                return str1;
            }
        }
        else { // l1 > l2
            bool flag = false;
            int i, j;
            for (i = 0; i < str1.length(); i+=str2.length()) {
                for (j = 0; j < str2.length(); j++) {
                    if (str2[j] != str1[i+j]) {
                        flag = true;
                    }
                }
                if (flag) {
                    break;
                }
            }
            return str1.substr(i);
        }
        
    }
};