Longest Common Prefix

描述

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

分析

从位置0开始，对每一个位置比较所有字符串，直到遇到一个不匹配。

纵向扫描

  1. // Longest Common Prefix
  2. // 纵向扫描，从位置0开始，对每一个位置比较所有字符串，直到遇到一个不匹配
  3. // 时间复杂度O(n1+n2+...)
  4. // @author 周倩 (http://weibo.com/zhouditty)
  5. class Solution {
  6. public:
  7.     string longestCommonPrefix(vector &strs) {
  8.         if (strs.empty()) return "";
  10.         for (int j = 0; j < strs[0].size(); ++j) { // 纵向扫描
  11.             for (int i = 1; i < strs.size(); ++i) {
  12.                 // 不会越界，请参考string::[]的文档
  13.                 if (strs[i][j] != strs[0][j])
  14.                     return strs[0].substr(0,j);
  15.             }
  16.         }
  17.         return strs[0];
  18.     }
  19. };

横向扫描

  1. // Longest Common Prefix
  2. // 横向扫描，每个字符串与第0个字符串，从左到右比较，直到遇到一个不匹配，
  3. // 然后继续下一个字符串
  4. // 时间复杂度O(n1+n2+...)
  5. class Solution {
  6. public:
  7.     string longestCommonPrefix(vector &strs) {
  8.         if (strs.empty()) return "";
  10.         int right_most = strs[0].size();
  11.         for (size_t i = 1; i < strs.size(); i++)
  12.             for (int j = 0; j < right_most; j++)
  13.                 if (strs[i][j] != strs[0][j])  // 不会越界，请参考string::[]的文档
  14.                     right_most = j;
  16.         return strs[0].substr(0, right_most);
  17.     }
  18. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/longest-common-prefix.html