每日一练(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;
}
推荐阅读
- 31日打卡|蓝桥杯真题31日冲刺国一 | 每日题解报告 第六天
- 31日打卡|蓝桥真题31日冲刺 | 每日三题题解报告 第二天
- 每日一题|牛客网HJ21 简单密码
- 每日leetcode——42. 接雨水
- Leetcode3无重复字符的最长子串(滑动窗口解法)
- 排序+|排序+ 前缀最值 寒假每日一题 奶牛过马路
- 每日leetcode——739. 每日温度
- 每日刷题———蓝桥杯真题|蓝桥杯2018第九届C语言B组省赛总决赛习题题解——习题A.换零钞(暴力枚举法)
- 每日leetcode——946. 验证栈序列
- #|C语言每日一练——第140天(抓交通肇事犯)