每日一练(35)(最长公共前缀)

title: 每日一练(35):最长公共前缀
【每日一练(35)(最长公共前缀)】categories:[剑指offer]
tags:[每日一练]
date: 2022/03/14
每日一练(35):最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
方法一:逐字符比较
思路分析 先第一个和第二个比,保存公共前缀,再和第三个比,以此类推

string longestCommonPrefix(vector& strs) { if (strs.size() == 0) { return ""; } string ans = strs[0]; //先从strs[0]开始,与后面一个比较 for (int i = 0; i < strs.size(); i++) { string s = ans; //保存上次的公共前缀 ans = ""; for (int j = 0; j < strs[i].size(); j++) { if (s[j] == strs[i][j]) { ans += s[j]; } else { //遇到不一样的就退出循环 break; } } if (ans == "") { break; } } return ans; }

方法二:双指针
算法流程:
先找出数组中字典序最小和最大的字符串,最长公共前缀即为这两个字符串的公共前缀
string longestCommonPrefix(vector& strs) { if (strs.size() == 0) { return ""; } const auto p = 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; }

    推荐阅读