最长公共前缀

文章目录

• 最长公共前缀
• 题目
• 函数原型
• 边界判断
• 算法设计：垂直扫描

题目

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

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

示例 1:

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

示例 2:

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

说明:

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

函数原型

C的函数原型：

char * longestCommonPrefix(char ** strs, int strsSize){} 

边界判断

if( strs == NULL || strsSize == 0) return ""; if(strsSize == 1) return strs[0]; 

算法设计：垂直扫描

思路：做一个遍历，以第一个单词为始，定义一个指针往后偏移，如果指针偏移的过程中有不同，就return，不然就一直遍历。

for(int index=0; index<strlen(strs[0]); index++) // 以第一个单词的长度做结束条件 { char tmp = strs[0][index]; // 记录第一个单词的第 index 个字母, 与后面的字母比较 for(int j=1; j<strsSize; j++){ // 和其它单词比较，不用和自己比了，所以从 1 开始 if( tmp != strs[j][index] || (!strs[j][index]) ){ // 其它单词的第 index 个字母不等于第一个单词第 index 个字母时、或者其它单词的字母已经被遍历完了          strs[0][index] = ''; // 返回相同的前缀，但破坏了原数据不太好 return strs[0]; } } } return strs[0]; // 所有单词的所有字母都相等时，返回全部 

完整代码：

char * longestCommonPrefix(char ** strs, int strsSize){ if( strs == NULL || strsSize == 0) return ""; if(strsSize == 1) return strs[0]; for(int index=0; index<strlen(strs[0]); index++) // 以第一个单词的长度做结束条件 { char tmp = strs[0][index]; // 记录第一个单词的第 index 个字母, 与后面的字母比较 for(int j=1; j<strsSize; j++){ // 和其它单词比较，不用和自己比了，所以从 1 开始 if( tmp != strs[j][index] || (!strs[j][index]) ){ // 其它单词的第 index 个字母不等于第一个单词第 index 个字母时、或者其它单词的字母已经被遍历完了          strs[0][index] = ''; // 返回相同的前缀，但破坏了原数据不太好 return strs[0]; } } } return strs[0]; // 所有单词的所有字母都相等时，返回全部 } 

垂直扫描的复杂度：

• 时间复杂度：
  $Theta(n^{2})$

  Θ(n2)

• 空间复杂度：
  $Theta(1)$

  Θ(1)