LC14.LongestCommonPrefix

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower", "flow", "flight"]
输出："fl"
示例 2：

输入：strs = ["dog", "racecar", "car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

#include <iostream>
#include <vector>
#include <algorithm>
//Solution1：横向扫描
class Solution_1
{
public:
	std::string longestCommonPrefix(std::vector<std::string>& strs)
	{
		if (!strs.size()) return "";
		std::string prefix = strs[0];
		int count = strs.size();
		for (int i = 1; i < count; ++i)
		{
			prefix = longestCommonPrefix(prefix, strs[i]);
			if (!prefix.size()) break;
		}
		return prefix;
	}
	std::string longestCommonPrefix(const std::string& str1, const std::string& str2)
	{
		int length = std::min(str1.size(), str2.size());
		int index = 0;
		while (index < length && str1[index] == str2[index])
		{
			++index;
		}
		return str1.substr(0, index);
	}
};

//Solution2:横向扫描
class Solution_2
{
public:
	std::string longestCommonPrefix(std::vector<std::string>& strs)
	{
		if (!strs.size()) return "";
		int length = strs[0].size();
		int count = strs.size();
		for (int i = 0; i < count; ++i)
		{
			char c = strs[0][i];
			for (int j = 1; j < count; ++j)
			{
				if (i == strs[j].size() || strs[j][i] != c)
					return strs[0].substr(0, i);
			}
		}
		return strs[0];
	}
};

//Solution3:分治
class Solution_3
{
public:
	std::string longestCommonPrefix(std::vector<std::string>& strs)
	{
		if (!strs.size()) return "";
		else return longestCommonPrefix(strs, 0, strs.size() - 1);
	}

	std::string longestCommonPrefix(const std::vector<std::string>& strs, int start, int end)
	{
		if (start == end) return strs[start];
		else
		{
			int mid = (start + end) / 2;
			std::string lcpLeft = longestCommonPrefix(strs, start, mid);
			std::string lcpRight = longestCommonPrefix(strs, mid + 1, end);
			return commonPrefix(lcpLeft, lcpRight);
		}
	}

	std::string commonPrefix(const std::string& lcpLeft, const std::string& lcpRight)
	{
		int minLength = std::min(lcpLeft.size(), lcpRight.size());
		for (int i = 0; i < minLength; ++i)
		{
			if (lcpLeft[i] != lcpRight[i]) return lcpLeft.substr(0, i);
		}
		return lcpLeft.substr(0, minLength);
	}
};

//Solution4:二分查找
class Solution_4
{
public:
	std::string longestCommonPrefix(std::vector<std::string>& strs)
	{
		if (!strs.size()) return "";
		int minLength = std::min_element(strs.begin(), strs.end(), [](const std::string& s, const std::string& t) {return s.size() < t.size(); })->size();
		int low = 0, high = minLength;
		while (low < high)
		{
			int mid = (high - low + 1) / 2 + low;
			if (isCommonPrefix(strs, mid)) low = mid;
			else high = mid - 1;
		}
		return strs[0].substr(0, low);

	}

	bool isCommonPrefix(const std::vector<std::string>& strs, int length)
	{
		std::string str0 = strs[0].substr(0, length);
		int count = strs.size();
		for (int i = 1; i < count; ++i)
		{
			std::string str = strs[i];
			for (int j = 0; j < length; ++j)
			{
				if (str0[j] != str[j]) return false;
			}
		}
		return true;
	}
};
//Solution5:sort排序后比较首尾
class Solution_5
{
	std::string longestCommonPrefix(std::vector<std::string>& strs)
	{
		std::sort(strs.begin(), strs.end());
		std::string ans = "";
		for (int i = 0; i < strs[0].size() && i < strs[strs.size() - 1].size(); ++i)
		{
			if (strs[0][i] == strs[strs.size() - 1][i]) ans += strs[0][i];
			else break;
		}
		return ans;
	}
};