LongestCommonPrefix

注意数组为空的情况！！！

题目描述

输入一组字符串，输出这些字符串共有的最长前缀

题目分析

二重循环，外层是字符串长度向后移动，内层是每个字符串依次比较。得到了最容易想到的解决方法：

string longestCommonPrefix(vector<string>& strs) {
	string s = "";
	int size = strs.size();
	if (size == 0)
		return s;
	int* lens = new int[size];
	int min= strs[0].length();
	for (int i = 1; i < size; ++i)
	{
		lens[i] = strs[i].length();
		if (lens[i] < min)
			min = lens[i];
	}
	char ch;
	bool flag = true;
	for (int i = 0; i < min && flag; ++i)//字符串长度
	{
		ch = strs[0][i];
		for (int j = 0; j < size; ++j)//遍历每个字符串
		{
			if (strs[j][i] != ch)
			{
				flag = false;
				break;
			}
		}
		if (flag)
			s = s + ch;
	}
	return s;
}

但是提交之后发现内存使用量太大，难道是因为我开了一个记录长度的数组？突然想到递归也是可以解决的。

查了一下其他人的做法，发现了自己的不足：需要返回的字符串prefix，不需要一个个字母地附加。当字符串数组strs不为空时，令prefix=strs[0]，然后外层遍历res的字符，内层遍历strs数组，利用strs[i].indexOf(prefix) != 0和prefix.substring(0, prefix.length() - 1)已有的函数。这样空间复杂度为O(1)。