leetcode：14. 最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例：

  1. 输入：strs = ["flower","flow","flight"]
  2. 输出："fl"
  1. 输入：strs = ["dog","racecar","car"]
  2. 输出：""
  3. 解释：输入不存在公共前缀。

解答 & 代码

纵向扫描比较

  1. class Solution {
  2. public:
  3.     string longestCommonPrefix(vector<string>& strs) {
  4.         // 1. 计算得到最短字符串长度，最长公共前缀长度不会超过最短字符串长度
  5.         int minLen = INT_MAX;
  6.         for(int i = 0; i < strs.size(); ++i)
  7.             minLen = min(minLen, (int)strs[i].size());
  9.         string result = "";
  10.         // 纵向遍历，比较所有字符串下标 j 的位置是否相同
  11.         for(int j = 0; j < minLen; ++j)
  12.         {
  13.             char ch = strs[0][j];
  14.             for(int i = 1; i < strs.size(); ++i)
  15.             {
  16.                 if(strs[i][j] != ch)    // 存在一个字符串位置 j 的字符不同，则停止
  17.                     return result;
  18.             }
  19.             result += ch;                // 所有字符串位置 j 的字符都相同，将该字符加到 result 
  20.         }
  21.         return result;
  22.     }
  23. };

复杂度分析：设字符串数组中有 N 个字符串，字符串的最短长度为 M

  • 时间复杂度 O(MN)：
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 12.60% 的用户
  4. 内存消耗：9 MB, 在所有 C++ 提交中击败了 47.21% 的用户