LeetCode_14: Longest Common Prefix - LeetCode

# 引言

题目链接：https://leetcode.com/problems/longest-common-prefix/description/

# 题目大意

给出一串单词，编写一个函数找到这串单词的最长公共前缀

**Hint:**If there is no common prefix, return an empty string "".

Example

Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

# 题解

# 一句话题解

遍历所有输入单词，由于是求解公共最长前缀，因此假设第一个单词为前缀后续比对只要发现对应位置字符不同即可终止，检测 index 缩减到当前比对位置，最后返回 0 到前缀所在结束 index 的子串即可

# 复杂度

时间复杂度 O(nk) , k 表示前缀的长度

空间复杂度 O(k)

# AC 代码

c++ 版本

	class Solution
	{
	public:
	string longestCommonPrefix(vector<string> &strs)
	{
	if (strs.size() <= 0)
	{
	return "";
	}
	string ans = strs[0];
	int ansIndex = ans.length();
	for (int i = 1; i < strs.size(); ++i)
	{
	int curLength = strs[i].length();
	for (int j = 0; j < ansIndex && j < curLength; ++j)
	{
	if (strs[i][j] != ans[j])
	{
	ansIndex = j;
	continue;
	}
	}
	ansIndex = ansIndex < curLength ? ansIndex : curLength;
	}
	return 0 == ansIndex ? "" : ans.substr(0, ansIndex);
	}
	};

go 版本

	func longestCommonPrefix(strs []string) string {
	lens := len(strs)
	if lens <= 0 {
	return ""
	}
	ans, ansIndex := strs[0], len(strs[0])
	for _, v := range strs {
	curLen := len(v)
	for i := 0; i < ansIndex && i < curLen; i++ {
	if v[i] != ans[i] {
	ansIndex = i
	continue
	}
	}
	if curLen < ansIndex {
	ansIndex = curLen
	}
	}
	return ans[0:ansIndex]
	}

LeetCode