## 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Horizontal scanning)

\n

Intuition

\n

For a start we will describe a simple way of finding the longest prefix shared by a set of strings .\nWe will use the observation that :

\n

\n\n

\n

Algorithm

\n

To employ this idea, the algorithm iterates through the strings , finding at each iteration the longest common prefix of strings When is an empty string, the algorithm ends. Otherwise after iterations, the algorithm returns .

\n \n

Figure 1. Finding the longest common prefix (Horizontal scanning)

\n

Java

\n
public String longestCommonPrefix(String[] strs) {\n    if (strs.length == 0) return "";\n    String prefix = strs;\n    for (int i = 1; i < strs.length; i++)\n        while (strs[i].indexOf(prefix) != 0) {\n            prefix = prefix.substring(0, prefix.length() - 1);\n            if (prefix.isEmpty()) return "";\n        }        \n    return prefix;\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : , where S is the sum of all characters in all strings.
• \n
\n

In the worst case all strings are the same. The algorithm compares the string with the other strings There are character comparisons, where is the sum of all characters in the input array.

\n
\n
• Space complexity : .\nWe only used constant extra space.
• \n
\n
\n

#### Approach #2 (Vertical scanning)

\n

Algorithm

\n

Imagine a very short string is at the end of the array. The above approach will still do 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.

\n

Java

\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0) return "";\n    for (int i = 0; i < strs.length() ; i++){\n        char c = strs.charAt(i);\n        for (int j = 1; j < strs.length; j ++) {\n            if (i == strs[j].length() || strs[j].charAt(i) != c)\n                return strs.substring(0, i);             \n        }\n    }\n    return strs;\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : , where S is the sum of all characters in all strings.\nIn the worst case there will be equal strings with length and the algorithm performs character comparisons.\nEven though the worst case is still the same as Approach #1, in the best case there are at most comparisons where is the length of the shortest string in the array.
• \n
• Space complexity : .\nWe only used constant extra space.
• \n
\n
\n

#### Approach #3 (Divide and conquer)

\n

Intuition

\n

The idea of the algorithm comes from the associative property of LCP operation. We notice that :\n\n, where is the longest common prefix in set of strings , \n

\n

Algorithm

\n

To apply the observation above, we use divide and conquer technique, where we split the problem into two subproblems and , where mid is . We use their solutions lcpLeft and lcpRight to construct the solution of the main problem . To accomplish this we compare one by one the characters of lcpLeft and lcpRight till there is no character match. The found common prefix of lcpLeft and lcpRight is the solution of the .

\n \n

Figure 2. Finding the longest common prefix of strings using divide and conquer technique

\n

Java

\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0) return "";    \n        return longestCommonPrefix(strs, 0 , strs.length - 1);\n}\n\nprivate String longestCommonPrefix(String[] strs, int l, int r) {\n    if (l == r) {\n        return strs[l];\n    }\n    else {\n        int mid = (l + r)/2;\n        String lcpLeft =   longestCommonPrefix(strs, l , mid);\n        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);\n        return commonPrefix(lcpLeft, lcpRight);\n   }\n}\n\nString commonPrefix(String left,String right) {\n    int min = Math.min(left.length(), right.length());       \n    for (int i = 0; i < min; i++) {\n        if ( left.charAt(i) != right.charAt(i) )\n            return left.substring(0, i);\n    }\n    return left.substring(0, min);\n}\n
\n

Complexity Analysis

\n

In the worst case we have equal strings with length \n

\n
\n
• \n

Time complexity : , where is the number of all characters in the array, \n Time complexity is . Therefore time complexity is .\n In the best case this algorithm performs comparisons, where is the shortest string of the array

\n
• \n
• \n

Space complexity : \n

\n
• \n
\n

There is a memory overhead since we store recursive calls in the execution stack. There are recursive calls, each store need space to store the result, so space complexity is \n

\n
\n\n

The 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 , 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:\n S[1...mid] is not a common string. This means that for each j > i S[1..j] is not a common string and we discard the second half of the search space.\n S[1...mid] is common string. This means that for for each i < 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.

\n \n

Figure 3. Finding the longest common prefix of strings using binary search technique

\n

Java

\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0)\n        return "";\n    int minLen = Integer.MAX_VALUE;\n    for (String str : strs)\n        minLen = Math.min(minLen, str.length());\n    int low = 1;\n    int high = minLen;\n    while (low <= high) {\n        int middle = (low + high) / 2;\n        if (isCommonPrefix(strs, middle))\n            low = middle + 1;\n        else\n            high = middle - 1;\n    }\n    return strs.substring(0, (low + high) / 2);\n}\n\nprivate boolean isCommonPrefix(String[] strs, int len){\n    String str1 = strs.substring(0,len);\n    for (int i = 1; i < strs.length; i++)\n        if (!strs[i].startsWith(str1))\n            return false;\n    return true;\n}\n
\n

Complexity Analysis

\n

In the worst case we have equal strings with length \n

\n
\n
• Time complexity : , where is the sum of all characters in all strings.
• \n
\n

The algorithm makes iterations, for each of them there are comparisons, which gives in total time complexity.

\n
\n
• Space complexity : .
• \n
\n

We only used constant extra space.

\n

## Further Thoughts / Follow up

\n

Let\'s take a look at a slightly different problem:

\n
\n

Given a set of keys S = , find the longest common prefix among a string q and S. This LCP query will be called frequently.

\n
\n

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:\n it is prefix of query string q\n each node along the path must contain only one child element. Otherwise the found path will not be a common prefix among all strings.\n* 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.

\n

Algorithm

\n

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 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.

\n \n

Figure 4. Finding the longest common prefix of strings using Trie

\n

Java

\n
public String longestCommonPrefix(String q, String[] strs) {\n    if (strs == null || strs.length == 0)\n         return "";  \n    if (strs.length == 1)\n         return strs;\n    Trie trie = new Trie();      \n    for (int i = 1; i < strs.length ; i++) {\n        trie.insert(strs[i]);\n    }\n    return trie.searchLongestPrefix(q);\n}\n\nclass TrieNode {\n\n    // R links to node children\n    private TrieNode[] links;\n\n    private final int R = 26;\n\n    private boolean isEnd;\n\n    // number of children non null links\n    private int size;    \n    public void put(char ch, TrieNode node) {\n        links[ch -\'a\'] = node;\n        size++;\n    }\n\n    public int getLinks() {\n        return size;\n    }\n    //assume methods containsKey, isEnd, get, put are implemented as it is described\n   //in  https://leetcode.com/articles/implement-trie-prefix-tree/)\n}\n\npublic class Trie {\n\n    private TrieNode root;\n\n    public Trie() {\n        root = new TrieNode();\n    }\n\n//assume methods insert, search, searchPrefix are implemented as it is described\n//in  https://leetcode.com/articles/implement-trie-prefix-tree/)\n    private String searchLongestPrefix(String word) {\n        TrieNode node = root;\n        StringBuilder prefix = new StringBuilder();\n        for (int i = 0; i < word.length(); i++) {\n            char curLetter = word.charAt(i);\n            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {\n                prefix.append(curLetter);\n                node = node.get(curLetter);\n            }\n            else\n                return prefix.toString();\n\n         }\n         return prefix.toString();\n    }\n}\n
\n

Complexity Analysis\nIn the worst case query has length and it is equal to all strings of the array.

\n
\n
• Time complexity : preprocessing , where is the number of all characters in the array, LCP query \n
• \n
\n

Trie build has time complexity. To find the common prefix of in the Trie takes in the worst case .

\n
\n
• Space complexity : \n
• \n
\n

We only used additional extra space for the Trie.

\n

Analysis written by: @elmirap.

\n
'