题目

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

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

示例 1：

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

示例 2：

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

提示：

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

解法

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
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int start = 0;
        string result = "";

        while(true)
        {
            char curChar = 0;
            for (auto& str : strs)
            {
                if (str[start] == '\0') { return result; }
                if (curChar == 0) { curChar = str[start]; }
                if (curChar != str[start])
                {
                    return result;
                }
            }
            result.append(1, curChar);
            start++;
        }
        return result;
    }
};

简单来说就是遍历这几个字符串同一位置的字符，任何字符串遇到'\0'就收手，这里用到了迭代器。

（没想到这道题第一次做就能跑出3ms的时间效率）