每日一题——最长公共前缀

题目

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围：0≤n≤5000， 0≤len(strs_i)≤5000

进阶：空间复杂度 O(1)，时间复杂度 O(n∗len)

示例1

输入：
["abca","abc","abca","abc","abcc"]
返回值：
"abc"

示例2

输入：
["abc"]
返回值：
"abc"

思路

以第一个字符串为基准，与其他字符串进行比较。从第一个字符开始，逐位比较，即可找出最长公共前缀。

解答代码

#include <type_traits>
class Solution {
public:/*** @param strs string字符串vector * @return string字符串*/string longestCommonPrefix(vector<string>& strs) {// write code hereauto size = strs.size();if (size == 0) {return "";} else if (size == 1) {return strs[0];}// 找出字符串的最小长度string::size_type min_str_size = strs[0].size();for (auto& str : strs) {min_str_size = min(min_str_size, str.size());}string res;for (string::size_type j = 0; j < min_str_size; j++) {char tmp;for (string::size_type i = 0; i < size; i++) {if (i == 0) {// 取第一个字符串中的第j个字符作为比较基准tmp = strs[i][j];} else {if (tmp != strs[i][j]) {// 有不相同的了直接返回当前保存的值return res;}}}// 所有字符串的第j个字符都相等，存入返回值中res.push_back(tmp);}return res;}
};