LeetCode-02-字符串寻找最大公因子

发表于 更新于 阅读次数： 本文字数： 686 阅读时长 ≈ 2 分钟

LeetCode算法题：字符串找最大公因子。

题目

LeetCode：LeetCode 75 - 学习计划-02-字符串最大公因子

对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

思路

如果存在最大公因子，最长的相同元素一定是str1与str2中短的那个。

方案A： 若存在字符串最大公因子，则str1或str2必定只有x元素。即str1与str2之间辗转对比一定能找到最终的x，否则不存在最大公因子。

方案B：字符串的公因子是按照长度定义，只需要找到字符串str1与str2长度的最大公因子，以次长度为基准，比对str1与str2的元素。

代码

方案A

辗转相除，以较短的字符串为基准，不断向后移动并缩减比对字符串的长度，也是希望找到长度的最大公因子。

image can't load. 长度上辗转相除 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
char* gcdOfStrings(char* str1, char* str2) 
{
    int n1 = strlen(str1);
    int n2 = strlen(str2);
    while(true)
    {
        if(n1==n2 && strncmp(str1,str2,n1)==0 ) //字符串长度相等
        {
            return str1;
        }
        else if(n1>n2 && strncmp(str1,str2,n2)==0) //str1长，向后移动
        {
            str1 += n2;
            n1 -= n2;
        }
        else if(n1<n2 && strncmp(str1,str2,n1)==0)
        {
            str2 += n1;
            n2 -= n1;
        }
        else 
        {
            return "";
        }
    }
}

方案B

如果考虑不到方案A的辗转相除，那么可以尝试找到长度公因子，并使用长度对应的元素分别与str1和str2后续的字符做比较，理论上应当完全一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//int gcd = iGcd(6,4);
int iGcd(int len1,int len2);
//int result = ("ABABAB","AB",2);
int iCheck(char *str1, char *str2, int len);

char* gcdOfStrings(char* str1, char* str2) {
     //str1与str2前n个元素不同
    for(int i=0;str1[i] && str2[i]; i++)
    {
        if(str1[i]!=str2[i])
        {
            return "";
        }
    }
    
    int n1 = strlen(str1);
    int n2 = strlen(str2);
    int result = iGcd(n1,n2);//找到长度最大公因子

    for(int len =result;len>0;len--) //例如偶数可能是4、2、1
    {
        if(n1%len || n2%len)
        {
            continue;
        }
        if(iCheck(str1,str2,len)==0)
        {
            str1[len] = '\0';
            return str1;
        }
    }

    return "";
}

//寻找长度的最大公因子
int iGcd(int len1,int len2)
{
    while(len1!=len2)
    {
        if(len1 > len2)
        {
            len1 -= len2;
        }
        else 
        {
            len2 -= len1;
        }
    }
    return len1;
}

int iCheck(char *str1, char *str2, int len)
{
    int i=0;
    //str1前len长度字符与后续对比
    for(int j=len; str1[j] ;j++)
    {
        if(str1[i]!=str1[j]) 
        {
            return 1;
        }
        i = (i+1)%len;
    }
	//str1前len长度字符与str2后续字符对比	
    for(int j=len; str2[j] ;j++)
    {
        if(str1[i]!=str2[j]) 
        {
            return 1;
        }
        i = (i+1)%len;
    }
    return 0;
}

————————— End —————————

“天长地久有时尽，此恨绵绵无绝期。”– 《长恨歌》