LeetCode 0014 - Longest Common Prefix
# Hints
- 水题 + Trie树
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
.
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z
.
# 题意
给定 个字符串,求这些字符串的最长公共前缀。
# 题解
设 表示第 个字符串的长度。
我们只需要选择一个最短的字符串 作为模式串,然后将 与剩下的每个字符串 进行前缀匹配,取匹配结果的最小值即可,时间复杂度为 。
事实上,上述思路的本质是运用了Trie树的思想。考虑用这 个字符串建立Trie树,然后从根节点出发不断前进,直到遇到任意一个节点,其子节点个数超过 ,或是走到叶子节点,则已求出最长公共前缀。
但是我们并不需要真的建出Trie树,只需要依次遍历每个字符串即可(就像前文所述的那样)。特地打上Trie树的标签的理由是它们在本质上的相同之处。
细节问题:
- 注意特判 的情况。
# AC代码
class Solution {
public:
string longestCommonPrefix(vector<string> & strs) {
// 特判
if (strs.empty()) {
return string("");
}
// 初始化
int len = strs[0].length();
for (int i = 1; i < strs.size(); i ++) {
len = min(len, (int)strs[i].length());
}
// 求解
for (int i = 1; i < strs.size(); i ++) {
for (int j = 0; j < min(len, (int)strs[i].length()); j ++) {
if (strs[i][j] != strs[0][j]) {
strs[i][j] = '*';
len = j;
break;
}
}
}
// 返回
return strs[0].substr(0, len);
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01