Longest Common Prefix

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.

Solution:

The requirement here is to find longest common prefix amongst an array of strings.

There are many approaches to this problem but the one that I am going to discuss here uses Trie to store the array of strings and then scan the trie to get the longest common prefix.

To know more about Trie, you can visit here.

Algorithm:

1) Store each string from the array of strings in Trie.

2) Get the deepest Trie Node such that all the nodes from the root of the trie to that node has only one children.

Link to Code

Space Complexity: O(n) where n is the number of unique characters in the array of string.

Time Complexity: O(n) for building the Trie (n is the number of unique characters in the array of string) and O(m) for finding the prefix (where m is the length of the prefix).