Given k strings, find the longest common prefix (LCP).
For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"
For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"
LeetCode上的原题，请参见我之前的博客Longest Common Prefix。
解法一：
class Solution { public: /** * @param strs: A list of strings * @return: The longest common prefix */ string longestCommonPrefix(vector<string> &strs) { if (strs.empty()) return ""; string res = ""; for (int j = 0; j < strs[0].size(); ++j) { char c = strs[0][j]; for (int i = 0; i < strs.size(); ++i) { if (j >= strs[i].size() || strs[i][j] != c) return res; } res.push_back(c); } return res; } };
解法二：
class Solution { public: /** * @param strs: A list of strings * @return: The longest common prefix */ string longestCommonPrefix(vector<string> &strs) { if (strs.empty()) return ""; for (int j = 0; j < strs[0].size(); ++j) { for (int i = 0; i < strs.size() - 1; ++i) { if (j >= strs[i].size() || j >= strs[i + 1].size() || strs[i][j] != strs[i + 1][j]) { return strs[i].substr(0, j); } } } return strs[0]; } };
本文转自博客园Grandyang的博客，原文链接：最长共同前缀[LintCode] Longest Common Prefix ，如需转载请自行联系原博主。
