引言
题目链接：https://leetcode.com/problems/longest-common-prefix/description/
题目大意
给出一串单词，编写一个函数找到这串单词的最长公共前缀
Hint:If there is no common prefix, return an empty string "".
- Example
|
1 2 3 4 5 6 |
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++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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] } |
