LeetCode14：Longest Common Prefix

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

要求找出字符串数组中所有字符串的最长公共前缀。

解题思路：两个字符串的最长公共前缀，其长度肯定不会超过最短的字符串的长度，设最短的字符串长度为m，那么只要比较这两个字符串的前m个字符即可。

每次得出两个字符串的最长公共前缀prefix后，再拿prefix作为新的字符串和数组中的下一个字符串比较，直到找出不相等的字符。如果数组中的某个字符串长度为0，或者求得的当前最长公共前缀的长度为0，就直接返回空字串。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
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])//其中strs[i][j]表示字符串数组中第i+1个字符串的第j+1个字符
					break;
			}
			prefix = prefix.substr(0, j);//每次得到两个字符串的最长公共前缀prefix后，再拿prefix作为新的字符串和数组中的下一个字符串比较
		}
		return prefix;
	}
};