您当前位置：首页 > php开源 > php教程 > leetcode笔记：Longest Common Prefix

leetcode笔记：Longest Common Prefix

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

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. 小结

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

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

------分隔线----------------------------

上一篇 JS通过prototype实现继承的简单示例:

下一篇 SSL/TLS Bar Mitzvah Attack 漏洞 [ 受诫礼(BAR-MITZVAH) ]

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点