Leetcode——14. Longest Common Prefix-白红宇

Leetcode——14. Longest Common Prefix

阅读量：3526 次

发布时间：2019-05-20

本文共 1151 字，大约阅读时间需要 3 分钟。

1. 概述

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

题目如上，意思就是在给定的一个字符串数组中，求取所有字符串中的最长公共前缀。

2. 编码

2.1 方法1

第一种方法是直接拿一个字符串与其它的字符串相比较，记录本次比较重最长公共前缀，遍历完之后就得到了最长的前缀字符串。复杂度是O(N*M)，N是数组的元素个数，M是取的第一个元素的长度

class Solution {public:    string longestCommonPrefix(vector
    
     & strs)     {        int len(strs.size());   //字符串数组中元素的个数        if(0 == len) return "";        if(1 == len) return strs[0];        if(2 == len && strs[0]==strs[1]) return strs[0];                      //方法2        int pos(0);             //公共字符串的最远端        string str(strs[0]);    //公共前缀                for(int i=1; i
     
       strs[i].length())            {                string temp = str;                for(int k=0; k

性能

2.2 方法2

这里先求取出字符串数组中最短的字符串长度，然后按照这个长度去遍历字符串数组，得到最后的最长公共前缀字符串。O(N*min_len)

class Solution {public:    string longestCommonPrefix(vector
    
     & strs)     {        int len(strs.size());   //字符串数组中元素的个数        if(0 == len) return "";        if(1 == len) return strs[0];        if(2 == len && strs[0]==strs[1]) return strs[0];                int min_len(123456789); //公共前缀的最大长度        for(int i=0; i

性能

你可能感兴趣的文章