leecode-C语言实现-14. 最长公共前缀

作者：IT小白 | 2024-04-18 12:59:28

踩

一、题目
在这里插入图片描述
二、解题思路
（1）思路一
数组中的所有字符串同时从第一个字符开始进行比较，如果都相等，复制到结果中，如果不相等，退出循环。第一个字符遍历完，需判断数组是否越界，表示某个字符串已经遍历完，结果中存的字符串就是最长前缀，退出循环。

三、VS-2017-测试代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define StrArrGroupNum 4
#define StrArrNum 3

char* longestCommonPrefix(char** strs, int strsSize);
char* CompareTwoStrCommon(char* str1, char* str2);
void InitStr(char* strarr, int strarrlen);
void CopyChar(char* str1, char str2);
void CopyString(char* str1, char* str2);
char* longestCommonPrefix_v1(char** strs, int strsSize);

void main() {
    char* StrArr[StrArrGroupNum][StrArrNum] = { { "flower", "flow", "flight" }, 
                                                { "dog","racecar","car" } ,
                                                {"a","a","b"},
                                                {"aac","a","ccc"}};
    int i,j;
    for ( i = 0; i < StrArrGroupNum; i++)
    {
        for ( j = 0; j < StrArrNum; j++)
        {
            printf("%s  ", StrArr[i][j]);
        }
        printf("res : %s\n",longestCommonPrefix(StrArr[i], StrArrNum));
        printf("res : %s\n", longestCommonPrefix_v1(StrArr[i], StrArrNum));
        printf("===============================\n\n");
    }
}

/*
1、同时比较所有字符串。
2、各字符相等的话，把字符复制到结果中。
3、各字符相等的话，直接返回结果。
*/
char* longestCommonPrefix_v1(char** strs, int strsSize)
{
    char tmp = strs[0][0];
    int res_size = 105;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    int j = 0;
    int flg = 0;//1：表示字符有不相等的情况出现。0：表示字符没有不相等的情况出现。
    memset(res, '\0', res_size);

    while (1)
    {
        //printf("tmp : %c, res : %s\n",tmp,res);
        for (i = 1; i < strsSize; i++)
        {
            if (tmp != strs[i][j])
            {
                flg = 1;
                break;
            }
        }
        if (flg)
        {
            break;
        }
        memcpy(res + strlen(res), &tmp, 1);
        j++;
        //判断数组是否越界
        for (i = 0; i < strsSize; i++)
        {
            if (strlen(strs[i]) <= j)
            {
                flg = 1;
                break;
            }
        }
        if (flg)
        {
            break;
        }
        tmp = strs[0][j];
    }
    return res;
}

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 1)
    {
        return strs[0];
    }
    int i;
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    char* tmp = (char*)malloc(sizeof(char) * res_size);
    size_t tmp_res_size = 0;

    //初始化数组
    InitStr(res, res_size);
    InitStr(tmp, res_size);

    for (i = 1; i < strsSize; i++)
    {
        printf("\nstr1 : %s, str2 : %s, tmp_res_size : %zd\n",strs[0], strs[i], tmp_res_size);
        CopyString(tmp,CompareTwoStrCommon(strs[0], strs[i]));
        if(strlen(tmp) == 0)
        {
            return tmp;
        }
        else if(tmp_res_size == 0)
        {   
            CopyString(res, tmp);
            tmp_res_size = strlen(tmp);
        }
        else if(strlen(CompareTwoStrCommon(res, tmp)) == 0)
        {
            return "";
        }
        else if (tmp_res_size > strlen(tmp))
        {
            CopyString(res, tmp);
            tmp_res_size = strlen(res);
        }
    }
    return res;
}

//实现的是最长公共前缀
char* CompareTwoStrCommon(char* str1, char* str2)
{
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    size_t str1_len = strlen(str1);
    size_t str2_len = strlen(str2);
    if (str1_len == 0 || str2_len == 0)
    {
        return "";
    }
    //初始化数组
    InitStr(res, res_size);
    while (str1[i] != '\0' && str2[i] != '\0')
    {
        if (str1[i] == str2[i])
        {
            CopyChar(res, str1[i]);
        }
        else if (str1[i] != str2[i])
        {
            break;
        }
        printf("str1[%d] : %c, str2[%d] : %c, res : %s\n", i, str1[i], i, str2[i], res);
        i++;
    }
    printf("++++++++++++++++\n");
    return res;
}

/*
//实现的是最长公共字符串
char* CompareTwoStrCommon(char* str1, char* str2)
{
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    int flg = 0;//两个字符串中是否出现相同的字符，出现：1，没有出现：0。
    size_t str1_len = strlen(str1);
    size_t str2_len = strlen(str2);
    if (str1_len == 0 || str2_len == 0)
    {
        return "";
    }
    //初始化数组
    InitStr(res, res_size);
    while (str1[i] != '\0' && str2[i] != '\0')
    {
        if (str1[i] == str2[i])
        {
            CopyChar(res, str1[i]);
            flg = 1;
        }
        else if(str1[i] != str2[i] && flg)
        {
            break;
        }
        printf("str1[%d] : %c, str2[%d] : %c, flg : %d,res : %s\n", i, str1[i], i, str2[i], flg, res);
        i++;
    }
    printf("++++++++++++++++\n");
    return res;
}
*/

void InitStr(char* strarr, int strarrlen)
{
    int i;
    for (i = 0; i < strarrlen; i++)
    {
        strarr[i] = '\0';
    }
}

void CopyChar(char* str1, char str2)
{
    memcpy(str1 + strlen(str1), &str2, 1);
}

void CopyString(char* str1, char* str2)
{
    memcpy(str1, str2, strlen(str2)+1);
}

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207

四、VS-2017代码测试截图
在这里插入图片描述
五、leecode提交代码
（1）版本一

char* longestCommonPrefix(char** strs, int strsSize);
char* CompareTwoStrCommon(char* str1, char* str2);
void InitStr(char* strarr, int strarrlen);
void CopyChar(char* str1, char str2);
void CopyString(char* str1, char* str2);

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 1)
    {
        return strs[0];
    }
    int i;
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    char* tmp = (char*)malloc(sizeof(char) * res_size);
    size_t tmp_res_size = 0;

    //初始化数组
    InitStr(res, res_size);
    InitStr(tmp, res_size);

    for (i = 1; i < strsSize; i++)
    {
        //printf("\nstr1 : %s, str2 : %s, tmp_res_size : %zd\n",strs[0], strs[i], tmp_res_size);
        CopyString(tmp,CompareTwoStrCommon(strs[0], strs[i]));
        if(strlen(tmp) == 0)
        {
            return tmp;
        }
        else if(tmp_res_size == 0)
        {   
            CopyString(res, tmp);
            tmp_res_size = strlen(tmp);
        }
        else if(strlen(CompareTwoStrCommon(res, tmp)) == 0)
        {
            return "";
        }
        else if (tmp_res_size > strlen(tmp))
        {
            CopyString(res, tmp);
            tmp_res_size = strlen(res);
        }
    }
    return res;
}

//实现的是最长公共前缀
char* CompareTwoStrCommon(char* str1, char* str2)
{
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    size_t str1_len = strlen(str1);
    size_t str2_len = strlen(str2);
    if (str1_len == 0 || str2_len == 0)
    {
        return "";
    }
    //初始化数组
    InitStr(res, res_size);
    while (str1[i] != '\0' && str2[i] != '\0')
    {
        if (str1[i] == str2[i])
        {
            CopyChar(res, str1[i]);
        }
        else if (str1[i] != str2[i])
        {
            break;
        }
        //printf("str1[%d] : %c, str2[%d] : %c, res : %s\n", i, str1[i], i, str2[i], res);
        i++;
    }
    //printf("++++++++++++++++\n");
    return res;
}

/*
//实现的是最长公共字符串
char* CompareTwoStrCommon(char* str1, char* str2)
{
    int res_size = 200;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    int flg = 0;//两个字符串中是否出现相同的字符，出现：1，没有出现：0。
    size_t str1_len = strlen(str1);
    size_t str2_len = strlen(str2);
    if (str1_len == 0 || str2_len == 0)
    {
        return "";
    }
    //初始化数组
    InitStr(res, res_size);
    while (str1[i] != '\0' && str2[i] != '\0')
    {
        if (str1[i] == str2[i])
        {
            CopyChar(res, str1[i]);
            flg = 1;
        }
        else if(str1[i] != str2[i] && flg)
        {
            break;
        }
        printf("str1[%d] : %c, str2[%d] : %c, flg : %d,res : %s\n", i, str1[i], i, str2[i], flg, res);
        i++;
    }
    printf("++++++++++++++++\n");
    return res;
}
*/

void InitStr(char* strarr, int strarrlen)
{
    int i;
    for (i = 0; i < strarrlen; i++)
    {
        strarr[i] = '\0';
    }
}

void CopyChar(char* str1, char str2)
{
    memcpy(str1 + strlen(str1), &str2, 1);
}

void CopyString(char* str1, char* str2)
{
    memcpy(str1, str2, strlen(str2)+1);
}

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

（2）版本二

char* longestCommonPrefix(char** strs, int strsSize)
{
    char tmp = strs[0][0];
    int res_size = 105;
    char* res = (char*)malloc(sizeof(char) * res_size);
    int i = 0;
    int j = 0;
    int flg = 0;//1：表示字符有不相等的情况出现。0：表示字符没有不相等的情况出现。
    memset(res,'\0',res_size);

    while (1)
    {
        //printf("tmp : %c, res : %s\n",tmp,res);
        for (i = 1; i < strsSize; i++)
        {
            if (tmp != strs[i][j])
            {
                flg = 1;
                break;
            }
        }
        if (flg)
        {
            break;
        }
        memcpy(res + strlen(res), &tmp, 1);
        j++;
        //判断数组是否越界
        for ( i = 0; i < strsSize; i++)
        {
            if (strlen(strs[i]) <= j)
            {
                flg = 1;
                break;
            }
        }
        if (flg)
        {
            break;
        }
        tmp = strs[0][j];
    }
    return res;
}
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

六、leecode提交截图
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/446075