LeetCode 1071. Greatest Common Divisor of Strings C++_公共循环节

Problem

题目链接

Solution

题意为：给定字符串str1，str2，找出这两字符串的最大的公共循环节

例如ababab和ab的最大公共循环节是ab

abababab和abab的最大公共循环节abab

那么，若str1和str2存在公共循环节，那么str1和str2的最小循环节应该是相同的

例如 abababab和abab的最小循环节都是ab，那么它们之间必定存在公共循环节

那么由最小循环节相同我们可以知道 str1+str2==str2+str1

否则肯定不存在公共循环节

那么怎么求最大公共循环节呢 即然str1和str2都是由同一个最小循环节重复若干次组成的

我们只要求出str1长度和str2长度的最大公约数就行了

class Solution {
public:
    
    int gcd(int n,int m){
        return m==0?n:gcd(m,n%m);
    }
    
    string gcdOfStrings(string str1, string str2) {
        if(str1+str2!=str2+str1) return "";
        return str1.substr(0,gcd(str1.length(),str2.length()));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12