最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
解决方案：
Approach 1: Horizontal scanning
Intuition
For a start we will describe a simple way of finding the longest prefix shared by a set of strings <math><semantics><annotation encoding="application/x-tex">LCP(S_1 \ldots S_n)</annotation></semantics></math>LCP(S1…Sn). We will use the observation that :
<math><semantics><annotation encoding="application/x-tex">LCP(S_1 \ldots S_n) = LCP(LCP(LCP(S_1, S_2),S_3),\ldots S_n)</annotation></semantics></math>LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)
Algorithm
Finding the longest common prefix
Figure 1. Finding the longest common prefix (Horizontal scanning)
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}
Complexity Analysis
Time complexity : O(S)O(S) , where S is the sum of all characters in all strings.
In the worst case all nn strings are the same. There are SS character comparisons, where SS is the sum of all characters in the input array.
Space complexity : O(1)O(1). We only used constant extra space.
Approach 2: Vertical scanning
Algorithm
Imagine a very short string is at the end of the array. The above approach will still do SS comparisons. One way to optimize this case is to do vertical scanning. We compare characters from top to bottom on the same column (same character index of the strings) before moving on to the next column.
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length() ; i++){
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j ++) {
if (i == strs[j].length() || strs[j].charAt(i) != c)
return strs[0].substring(0, i);
}
}
return strs[0];
}
Complexity Analysis
- Time complexity :O(S) , where S is the sum of all characters in all strings.
- Space complexity : O(1). We only used constant extra space.
Approach 3: Divide and conquer
Intuition
The idea of the algorithm comes from the associative property of LCP operation.
Algorithm
To apply the observation above, we use divide and conquer technique,
Finding the longest common prefix
Figure 2. Finding the longest common prefix of strings using divide and conquer technique
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return longestCommonPrefix(strs, 0 , strs.length - 1);
}
private String longestCommonPrefix(String[] strs, int l, int r) {
if (l == r) {
return strs[l];
}
else {
int mid = (l + r)/2;
String lcpLeft = longestCommonPrefix(strs, l , mid);
String lcpRight = longestCommonPrefix(strs, mid + 1,r);
return commonPrefix(lcpLeft, lcpRight);
}
}
String commonPrefix(String left,String right) {
int min = Math.min(left.length(), right.length());
for (int i = 0; i < min; i++) {
if ( left.charAt(i) != right.charAt(i) )
return left.substring(0, i);
}
return left.substring(0, min);
}
Approach 4: Binary search
he idea is to apply binary search method to find the string with maximum value L, which is common prefix of all of the strings. The algorithm searches space is the interval <math><semantics><annotation encoding="application/x-tex">(0 \ldots minLen)</annotation></semantics></math>(0…minLen), where minLen is minimum string length and the maximum possible common prefix. Each time search space is divided in two equal parts, one of them is discarded, because it is sure that it doesn't contain the solution. There are two possible cases:
-
S[1...mid]is not a common string. This means that for eachj > i S[1..j]is not a common string and we discard the second half of the search space. -
S[1...mid]is common string. This means that for for eachi < j S[1..i]is a common string and we discard the first half of the search space, because we try to find longer common prefix.
Figure 3. Finding the longest common prefix of strings using binary search technique
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
int minLen = Integer.MAX_VALUE;
for (String str : strs)
minLen = Math.min(minLen, str.length());
int low = 1;
int high = minLen;
while (low <= high) {
int middle = (low + high) / 2;
if (isCommonPrefix(strs, middle))
low = middle + 1;
else
high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);
}
private boolean isCommonPrefix(String[] strs, int len){
String str1 = strs[0].substring(0,len);
for (int i = 1; i < strs.length; i++)
if (!strs[i].startsWith(str1))
return false;
return true;
}
Further Thoughts / Follow up
Let's take a look at a slightly different problem:
We could optimize LCP queries by storing the set of keys S in a Trie. For more information about Trie, please see this article Implement a trie (Prefix trie). In a Trie, each node descending from the root represents a common prefix of some keys. But we need to find the longest common prefix of a string q and all key strings. This means that we have to find the deepest path from the root, which satisfies the following conditions:
- it is prefix of query string
q - each node along the path must contain only one child element. Otherwise the found path will not be a common prefix among all strings.
- the path doesn't comprise of nodes which are marked as end of key. Otherwise the path couldn't be a prefix a of key which is shorter than itself.
Algorithm
The only question left, is how to find the deepest path in the Trie, that fulfills the requirements above. The most effective way is to build a trie from <math><semantics><annotation encoding="application/x-tex">[S_1 \ldots S_n]</annotation></semantics></math>[S1…Sn] strings. Then find the prefix of query string q in the Trie. We traverse the Trie from the root, till it is impossible to continue the path in the Trie because one of the conditions above is not satisfied.
Finding the longest common prefix using Trie
Figure 4. Finding the longest common prefix of strings using Trie
public String longestCommonPrefix(String q, String[] strs) {
if (strs == null || strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
Trie trie = new Trie();
for (int i = 1; i < strs.length ; i++) {
trie.insert(strs[i]);
}
return trie.searchLongestPrefix(q);
}
class TrieNode {
// R links to node children
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
// number of children non null links
private int size;
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
size++;
}
public int getLinks() {
return size;
}
//assume methods containsKey, isEnd, get, put are implemented as it is described
//in https://leetcode.com/articles/implement-trie-prefix-tree/)
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
//assume methods insert, search, searchPrefix are implemented as it is described
//in https://leetcode.com/articles/implement-trie-prefix-tree/)
private String searchLongestPrefix(String word) {
TrieNode node = root;
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
prefix.append(curLetter);
node = node.get(curLetter);
}
else
return prefix.toString();
}
return prefix.toString();
}
}
GO 语言解决方案：
package main
import (
"fmt"
"strings"
)
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < len(strs); i++ {
for !strings.HasPrefix(strs[i], prefix) {
prefix = prefix[0 : len(prefix)-1]
if len(strings.TrimSpace(prefix)) == 0 {
return ""
}
}
}
return prefix
}
func main() {
//slice := []string{"flower","flow","flight"}
slice := []string{"leets","leetcode","leet","leeds"}
//slice := []string{"dog","racecar","car"}
fmt.Printf("最长公共前缀:%+v",longestCommonPrefix(slice))
}
