[0014] 最长公共前缀
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
题目解析
不确定性
方法一：水平扫描法
分析
思路
- 对于容器内每一个字符串，从第一个字符向后进行比较
- 一旦出现某两个字符串中同一位置的字符不同的情况，即可返回结果
注意
- 同一位置的字符比较，应是比到最短字符串的最后一个字符
- 如果整个遍历完成都没有出现同位置字符不相同的情况，则返回容器内最短的字符串，这是因为在开始，停止条件被设定为最短字符串的长度
知识点
复杂度
- 时间复杂度O(m*n)，其中m为容器内字符串数量，n为其中最短字符串的长度
- 空间复杂度O(1)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0){
return "";
}
int minLen = INT_MAX;
for (vector<string>::size_type i = 0; i < strs.size(); i++){
if (strs[i].size() < minLen){
minLen = strs[i].size();
}
}
string::size_type j = 0;
for (; j < minLen; j++){
for (vector<string>::size_type i = 1; i < strs.size(); i++){
if (strs[i][j] != strs[i - 1][j]){
return strs[i].substr(0, j);
}
}
}
return strs[0].substr(0, j);
}
|
方法二：二分查找法
分析
- 取最短字符串的长度作为前缀的最大长度minLen
- 将minLen分为两部分，[0, mid-1]以及[mid, minLen]
- 当左边区间所对应的字符串是公共前缀时，可以继续向右边区间延展，即增大mid的值
- 当左边区间所对应的字符串不是公共前缀是，则需要缩小左侧的区间，即减小mid的值
思路
注意
- 为了确保每次的查找时prefix存在，因此low应从1开始，而不是0开始
知识点
- 字符串中截取子串的方法substr()
- 二分查找法
复杂度
- 时间复杂度 mnO(log(n))，其中m为容器内字符串的数量，n为字符串长度
- 空间复杂度O(1)
代码
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
28
29
30
31
32
33
34
35
36
37
| bool isCommonPrefix(vector<string>& strs, string prefix){
for (string str : strs){
if (str.substr(0, prefix.size()) != prefix){
return false;
}
}
return true;
}
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0){
return "";
}
if (strs.size() == 1){
return strs[0];
}
int minLen = INT_MAX;
for (string str : strs){
minLen = min(minLen, static_cast<int>(str.size()));
}
int low = 1;
int high = minLen;
while (low <= high){
int mid = (low + high) / 2;
string prefix = strs[0].substr(0, mid);
if (isCommonPrefix(strs, prefix)){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return strs[0].substr(0, (low + high) / 2);
}
|
方法三：字典树法
分析
- 将容器内所有字符串存储到字典树中。在字典树中，从根向下的每一个节点都代表一些键值的公共前缀。需要找到一条最深的公共路径（路径上的节点有且只有一个孩子）作为最长公共前缀。
思路
- 利用容器内的字符串建立字典树
- 可能存在的最长公共前缀为容器内最短的字符串
- 利用字符串中的字符，从字典树的根节点向下查找
注意
知识点
复杂度
- 时间复杂度 O(m*n)，其中m为容器内字符串的数量，n为字符串长度
- 空间复杂度 O(m*n)
代码
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
class TrieNode{
public:
TrieNode* next[26];
bool isword;
int numLinks;
TrieNode(){
numLinks = 0;
memset(next, NULL, sizeof(next));
isword = false;
}
~TrieNode(){
for (int i = 0; i < 26; i++){
if (next[i]) delete next[i];
}
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
~Trie(){
delete root;
}
void insert(string word){
TrieNode* p = root;
for (int i = 0; i<(int)word.size(); i++){
if (p->next[word[i] - 'a'] == NULL){
p->next[word[i] - 'a'] = new TrieNode();
p->numLinks++;
}
p = p->next[word[i] - 'a'];
}
p->isword = true;
}
bool search(string word){
TrieNode *p = root;
for (int i = 0; i<(int)word.size() && p; i++){
p = p->next[word[i] - 'a'];
}
return p&&p->isword;
}
bool startsWith(string prefix){
TrieNode*p = root;
for (int i = 0; i<(int)prefix.size() && p; i++){
p = p->next[prefix[i] - 'a'];
}
return p;
}
};
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0){
return "";
}
if (strs.size() == 1){
return strs[0];
}
Trie* trie = new Trie();
for (int i = 0; i < strs.size(); i++){
trie->insert(strs[i]);
}
int minLen = INT_MAX;
for (string str : strs){
if (str.size() < minLen){
minLen = str.size();
}
}
string longestCommonPrefix = "";
TrieNode* node = trie->root;
string tmpStr = strs[0].substr(0, minLen);
for (int j = 0; j < tmpStr.size(); j++){
char c = tmpStr[j];
if (node->next[c - 'a'] && node->numLinks == 1 && !node->isword){
longestCommonPrefix += c;
node = node->next[c - 'a'];
}
else{
break;
}
}
return longestCommonPrefix;
}
|
相关题目