博文中会简要介绍Leetcode P0014题目分析及解题思路。
“Longest Common Prefix”是一道比较简单的题目，主要是考察优化时间复杂度。
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”
核心思路围绕如何将时间复杂度控制在O(n)来展开，考虑到公共前缀串必须满足每一个字符串都有这个前缀串，则可以任意使用一个串作为公共前缀串，然后用它去比较每一个字符串的前缀，保留相同前缀，去掉剩余部分。
以下是Java的题解代码实现。
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
StringBuilder longestCommonPrefix = new StringBuilder(strs[0]);
for (int idx=1; idx<strs.length; ++idx) {
longestCommonPrefix = this.updatePrefix(strs[idx], longestCommonPrefix);
}
return longestCommonPrefix.toString();
}
private StringBuilder updatePrefix(String str, StringBuilder lcp) {
int len = Math.min(str.length(), lcp.length());
StringBuilder newCommonPrefix = new StringBuilder();
for (int itr=0; itr<len; ++itr) {
if (lcp.charAt(itr) == str.charAt(itr))
newCommonPrefix.append(lcp.charAt(itr));
else
break;
}
return newCommonPrefix;
}
}
以下是C++的题解代码实现。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0)
return "";
string longgest_common_prefix = strs[0];
for (int itr=1; itr<strs.size(); ++itr) {
longgest_common_prefix = this->update_lcp(strs[itr], longgest_common_prefix);
}
return longgest_common_prefix;
}
private:
string update_lcp(string str, string lcp) {
int len = min(str.length(), lcp.length());
// 需要注意的是，C++ string类型未规定以'\0'结尾，所以不能用强制添加'\0'的方式进行截取
string new_lcp = "";
for (int idx=0; idx<len; ++idx) {
if (str[idx] == lcp[idx])
new_lcp += str[idx];
else
break;
}
return new_lcp;
}
};