首页 > 其他 > 详细

14. Longest Common Prefix

时间:2018-01-18 21:53:44      阅读:232      评论:0      收藏:0      [点我收藏+]

14. Longest Common Prefix

题目

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

解析

  • leetcode官网给出了水平,垂直,二分,trie树的方法;但是感觉都需要把所有字符串遍历一遍,考虑用简单的水平遍历
class Solution_14 {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.size() == 0)
        {
            return ""; //返回NULL 错误
        }
        if (strs.size() == 1)
        {
            string str = strs[0];
            return str;
        }
        string ret = strs[0];
        int max_comlen = ret.size();
        int j = 0;
        for (int i = 1; i < strs.size(); i++)
        {
            j = 0;
            while (strs[i][j] == ret[j] && j < ret.size()) //优化:记录上一次匹配最远的位置,下一次不超过这个距离
            {
                j++;
            }
            max_comlen = min(max_comlen, j); //取的是最小长度的公共子串;min=('a','a','b')=0;
        }
        return ret.substr(0, max_comlen);
    }
};

题目来源

14. Longest Common Prefix

原文:https://www.cnblogs.com/ranjiewen/p/8313049.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!