【LeetCode 14】最长公共前缀
2024-09-01 23:47:30
【题解】
二分最长前缀的长度。
然后暴力把第2..n个字符串和第1个字符串的前mid个字符匹配。
还有一种比较厉害的算法。
把这n个字符串加入到字典树当中去。
然后根节点到第一个有分支的节点路径上的点形成的字符串就是最长前缀了。
【代码】
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int l = 1,r = 0,ans = -1;
for (int i = 0;i < (int)strs.size();i++){
r = max(r,(int)strs[i].size());
}
while (l<=r){
int mid = (l+r)/2;
int ok = 1;
for (int i = 1;i < (int)strs.size();i++){
for (int j = 0;j < mid;j++)
if (strs[i][j]!=strs[0][j]){
ok = 0;
break;
}
if (!ok) break;
}
if (ok){
l = mid+1;
ans = mid;
}else r = mid-1;
}
string temp = "";
for (int i = 0;i < ans;i++) temp += strs[0][i];
return temp;
}
};
最新文章
- [AlwaysOn Availability Groups]排查:AG超过RPO
- My97日期控件 选择日期区间
- 创建Spring容器
- Selenium2学习-025-WebUI自动化实战实例-023-页面快照截图应用之一 -- 常规截图(全页面)
- Android 之 JSON操作
- Js替换地址栏参数
- Python学习笔记五--条件和循环
- 今天上传公司服务器出现的.net framework版本错误问题
- 轻量级的数据交换语言(JSON)
- 查锁住的表,以及kill进程,Oracle常用语句
- 0x00000000该内存不能为read
- FileStream:The process cannot access the file because it is being used by another process
- 关于金额,重量等浮点数的数据库字段设计(用Int,Long代替浮点数计算)
- 并行cmd
- IDEA+Maven配置MyBatis的初体验(坑点总结)
- 如何重写Java中的equals方法
- Vue-admin工作整理(十六):Ajax-axios进行请求封装+拦截器
- Ubuntu环境下mysql常见的操作
- 「Android」GreenDao
- hdu-2089 不要62 基础DP 模板
热门文章
- 怀旧浪潮来袭,小霸王游戏、windows95......曾经的经典哪些能戳中你的心怀?
- SQL中的DQL查询语句
- 【leetcode】901. Online Stock Span
- 关于scrub的详细分析和建议
- ajaxfileupload异步上传
- vue-element-admin安装失败的问题
- [bzoj2456]mode 题解
- python locust_TaskSet声明任务的典型方法是使用task装饰器的两种方法
- CSS 随记
- (3)C++复合类型