Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
最长公共前缀最快的方法应该是使用后缀数组,但这里仅仅简单的使用了二重遍历,不过已经能提交leetcode了,面试的时候如果要是会后缀数组,应该很牛逼了,不过我不会,所以这里就是简单的两个两个遍历,用前两个的最长前缀后第三个求最长前缀,然后以此进行。
#include<iostream> #include<vector> #include<string> using namespace std; string longestCommonPrefix(vector<string> &strs) { int size = strs.size(),i,j; if(size == 0)return ""; string prefix = strs[0]; for(i = 1;i < size;++i) { int length = min(prefix.size(),strs[i].size()); if(length == 0)return ""; for(j = 0;j < length;++j)//每次求两个string的前缀 { if(prefix[j] != strs[i][j]) break; } prefix = prefix.substr(0,j);//更新当前的前缀 } return prefix; } int main() { int n,i; while(cin >> n) { vector<string> strs(n); for(i = 0;i < n;++i)cin >> strs[i]; cout << longestCommonPrefix(strs) << endl; } }