14 Longest Common Prefix 最長公共前綴
Description:
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:
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.
題目描述:
編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 ""川队。
示例:
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴箩艺。
說明:
所有輸入只包含小寫字母 a-z 。
思路:
- 先遍歷選出最短的詞, 在最短的詞中用二分法選擇子串
-
字典樹/前綴樹
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
代碼:
C++:
struct Node
{
char c;
int level;
int child;
unordered_map<char, Node*> map;
Node(char c)
{
this -> c = c;
level = 0;
child = 0;
}
Node() {}
};
class PreTree
{
private:
Node* head;
public:
PreTree()
{
head = new Node();
}
void insert(string str)
{
if (str.size() == 0) return;
int size = str.size();
// c_str()生成一個(gè)指針, 指向'\0'結(jié)尾的數(shù)組
// data()生成的數(shù)組不包括'\0'
char* c = (char*)str.data();
Node* p = head;
for (int i = 0; i < size; i++)
{
(p -> level)++;
// end()返回一個(gè)指向?qū)ο笕萜鹘Y(jié)尾的迭代器
if (p -> map.find(c[i]) == p -> map.end())
{
Node* new_node = new Node(c[i]);
p -> map[c[i]] = new_node;
}
// *iterator -> (key, value)
// second即指向value
p = p -> map.find(c[i]) -> second;
}
(p -> child)++;
}
bool findHelper(string str, int n)
{
if (str.size() == 0) return false;
Node* p = head;
int size = str.size();
char* c = (char*)str.data();
for (int i = 0; i < size; i++)
{
if (p -> map.find(c[i]) == p -> map.end())
{
return false;
}
else
{
int len = p -> map.find(c[i]) -> second -> level + p -> map.find(c[i]) -> second -> child;
if (len != n)
{
return false;
}
}
p = p -> map.find(c[i]) -> second;
}
return true;
}
};
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
if (strs.size() == 0) return "";
if (strs.size() == 1) return strs[0];
int size = strs.size();
string s = strs[0];
int len = s.size();
int length = 0;
PreTree pre;
for (int i = 0; i < size; i++)
{
pre.insert(strs[i]);
}
string help;
for (int i = 0; i < len; i++)
{
help = s.substr(0, i + 1);
if (pre.findHelper(help, size))
{
length++;
}
else
{
break;
}
}
return s.substr(0, length);
}
};
Java:
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
if (strs.length == 1) return strs[0];
int min = Integer.MAX_VALUE;
for (String str : strs) min = Math.min(min, str.length());
int low = 1;
int high = min;
while (low <= high) {
int mid = (low + high) / 2;
if (isStartsWith(strs, mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, (low + high) / 2);
}
private boolean isStartsWith(String[] strs, int mid) {
String start = strs[0].substring(0, mid);
for (int i = 0; i < strs.length; i++) {
if (!strs[i].startsWith(start)) {
return false;
}
}
return true;
}
}
Python:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
# Python中字符串可以按ASCII碼比較大小
s1 = min(strs)
s2 = max(strs)
for i, s in enumerate(s1):
if s != s2[i]:
return s2[:i]
return s1
