国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > leetcode笔记:Longest Common Prefix

leetcode笔记:Longest Common Prefix

来源:程序员人生   发布时间:2016-03-03 09:08:16 阅读次数:2205次

1. 题目描写

Write a function to find the longest common prefix string amongst an array of strings.

2. 题目分析

题目的大意是,给定1组字符串,找出所有字符串的最长公共前缀。

对照两个字符串的最长公共前缀,其前缀的长度肯定不会超过两个字符串中较短的长度,设最短的字符串长度为n,那末只要比较这两个字符串的前n个字符便可。

使用变量prefix保存两个字符串的最长公共前缀,再将prefix作为1个新的字符串与数组中的下1个字符串比较,以此类推。
1个特殊情况是,若数组中的某个字符串长度为0,或求得确当前最长公共前缀的长度为0,就直接返回空字符串。

3. 示例代码

#include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: string longestCommonPrefix(vector<string> &strs) { if (strs.size() == 0) return ""; string prefix = strs[0]; for (int i = 1; i < strs.size(); ++i) { if (prefix.length() == 0 || strs[i].length() == 0) return ""; int len = prefix.length() < strs[i].length() ? prefix.length() : strs[i].length(); int j; for (j = 0; j < len; ++j) { if (prefix[j] != strs[i][j]) break; } prefix = prefix.substr(0,j); } return prefix; } };

这里写图片描述

4. 小结

该题思路不难,而且还有几种类似的解决思路,在实现时需要做到尽可能减少比较字符的操作次数。

版权声明:本文为博主原创文章,未经博主允许不得转载。

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生