1. 題目描寫
Write a function to find the longest common prefix string amongst an array of strings.
2. 題目分析
題目的大意是，給定1組字符串，找出所有字符串的最長公共前綴。
對照兩個字符串的最長公共前綴，其前綴的長度肯定不會超過兩個字符串中較短的長度，設最短的字符串長度為n，那末只要比較這兩個字符串的前n個字符便可。
使用變量prefix保存兩個字符串的最長公共前綴，再將prefix作為1個新的字符串與數組中的下1個字符串比較，以此類推。
1個特殊情況是，若數組中的某個字符串長度為0，或求得確當前最長公共前綴的長度為0，就直接返回空字符串。
3. 示例代碼
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string> &strs)
{
if (strs.size() == 0)
return "";
string prefix = strs[0];
for (int i = 1; i < strs.size(); ++i)
{
if (prefix.length() == 0 || strs[i].length() == 0)
return "";
int len = prefix.length() < strs[i].length() ? prefix.length() : strs[i].length();
int j;
for (j = 0; j < len; ++j)
{
if (prefix[j] != strs[i][j])
break;
}
prefix = prefix.substr(0,j);
}
return prefix;
}
};
4. 小結
該題思路不難，而且還有幾種類似的解決思路，在實現時需要做到盡可能減少比較字符的操作次數。
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
