最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例1

输入：strs = ["flower","flow","flight"]
输出："fl"
1
2

示例 2

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
1
2
3

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

思路/解法

方式一

线性遍历，判断每一列是否相同，不相同则跳出，取出最长公共前缀即可。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int index = 0;
	    bool flag;
	    char c;
        if(strs.empty() || strs[0] == "")
            return "";

        if (strs.size() == 1)
		    return strs[0];
	    while (index < strs[0].length())
	    {
		    flag = false;
		    for (int i = 0; i < strs.size(); i++)
		    {
			    c = strs[0][index];
			    if (c != strs[i][index])
			    {
				    flag = true;
				    break;
			    }
		    }

		    if (flag)
		    {
			    break;
		    }

		    index++;
	    }
        return strs[0].substr(0,index);
    }
};
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

方式二

先获取数组中各个字符串字典序最小和最大的两个串，最长公共前缀即为这两个字符串的公共前缀。

TIPS：关于何为字典序，可以百度搜索理解。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty())
			return "";
		auto p = std::minmax_element(strs.begin(), strs.end());//获取数组中各个字符串字典序最小和最大的两个串。
		for (int i = 0; i < p.first->size(); i++)
		{
			if (p.first->at(i) != p.second->at(i))
				return p.first->substr(0, i);
		}
		return *p.first;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14