LeetCode之最长公共前缀（十四）

目录

题目

解题

方法一、暴力法

方法二、巧用STL函数

题目

（原题链接：https://leetcode-cn.com/problems/longest-common-prefix）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

解题

方法一、暴力法

分析：最笨最暴力的方法就是所有字符串遍历一遍，当然最终外循环次数是由最短的字符串长度决定的。方法的原理很简单就不过多解释了，具体请看代码和注释。但是需要说明的一点，编码过程中需要注意边界等越界问题。

代码：

  

   

    

     

    
    

     

      // C++
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 string longestCommonPrefix(vector<string>& strs) {
     
    
   

    

     

    
    

     
 int len = strs.size();
     
    
   

    

     

    
    

     
 // strs为空，所以返回空
     
    
   

    

     

    
    

     
 if (len == 0) 
     
    
   

    

     

    
    

     
 return "";
     
    
   

    

     

    
    

     
 // 只有一个字符串，返回值肯定就是它自己
     
    
   

    

     

    
    

     
 if (len == 1) 
     
    
   

    

     

    
    

     
 return strs[0];
     
    
   

    

     

    
    

     
 for (int i = 0; ; i ++) {
     
    
   

    

     

    
    

     
 // 外循环时，先检测向量数组[0]的长度，因为不确定有没有[1]元素，事实上，这个判断可以去掉，
     
    
   

    

     

    
    

     
 // 加上只是为了在一定情况下避免进入内循环的资源浪费
     
    
   

    

     

    
    

     
 if (i >= strs[0].size()) 
     
    
   

    

     

    
    

     
 return strs[0];
     
    
   

    

     

    
    

     
 char ch = strs[0][i];
     
    
   

    

     

    
    

     
 // 内循环次数是由数组元素个数决定的
     
    
   

    

     

    
    

     
 for (int j = 0; j < len; j ++) { 
     
    
   

    

     

    
    

     
 // 条件1和上一行对元素[0]判断是一致的；条件2是在扣题，保证最长公共子串
     
    
   

    

     

    
    

     
 if (i >= strs[j].size() || ch != strs[j][i]) 
     
    
   

    

     

    
    

     
 return strs[0].substr(0,i);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return strs[0];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n+m）。

空间复杂度：O（1）。

执行结果：

方法二、巧用STL函数

分析：首先巧妙使用sort函数先排序，利用其自身特点对公共子串的后一位排序（公共子串有可能为空），然后以排序后的元素[0]的字符串长度开始遍历。编码简单了一些，但是复杂度并没有降低，可以对比方法一和方法二的Runtime时间。

代码：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 string longestCommonPrefix(vector<string>& strs) {
     
    
   

    

     

    
    

     
 if (strs.size() == 0) 
     
    
   

    

     

    
    

     
 return "";
     
    
   

    

     

    
    

     
 if (strs.size() == 1) 
     
    
   

    

     

    
    

     
 return strs[0];
     
    
   

    

     

    
    

     
 // 先排序
     
    
   

    

     

    
    

     

       sort(strs.begin(),strs.end());
     
    
   

    

     

    
    

     
 string sb = strs.front();
     
    
   

    

     

    
    

     
 string se = strs.back();
     
    
   

    

     

    
    

     
 int len = min(sb.size(), se.size()); 
     
    
   

    

     

    
    

     
 for(int i = 0; i < len; i++) {
     
    
   

    

     

    
    

     
 // 后比较
     
    
   

    

     

    
    

     
 if (sb[i] != se[i])
     
    
   

    

     

    
    

     
 return sb.substr(0,i);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return sb;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n+m）。

空间复杂度：O（1）。

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/106881280