Longest Common Prefix

发表于 | 分类于

Longest Common Prefix

题目描述：

给定一组字符串，找到这组字符串中最长的公共前缀。

例子：

具体描述可以看LeetCode14

解题思路：

首先最长公共前缀肯定是小于等于所有字符串中的最短长度的；所以先找到字符串数组中的最短长度；然后是一个一个的判断在这个长度范围内是否所有的字符串都是以该字符为前缀即可。

代码如下：

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
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        //如果是空字符串数组直接返回空
        string res = "";
        int min_length = INT_MAX;
        for (auto &s : strs){
            min_length = min(min_length, (int)s.size());
        }//找到所有字符串中最短的长度
        for (int i = 0; i < min_length; i++){
            char prefix = strs[0][i];
            bool flag = true;
            //提取第i位的字符
            for (auto &s : strs){
                if (s[i] != prefix){
                    flag = false;
                    break;
                }
            }//判断所有的字符串是否都含有该字符
            if (flag == false) 
                return res;
                //标签为false的情况直接返回
            else {
                res = res + prefix;
                //否则加上该位字符
            }
        }
        return res;
    }
};