# 0014. Longest Common Prefix

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0014-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 `""`.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= strs.length <= 200`
* `0 <= strs[i].length <= 200`
* `strs[i]` consists of only lower-case English letters.

```
Input: strs = ["flower","flow","flight"]
Output: "fl"

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Instead of sorting the list of strings and find the answer between the longest string and shortest string, **we could use the Trie data structure to find the answer.&#x20;*****(Refer to*** [***0208. Implement Trie***](https://yyloumike.gitbook.io/leetcode/mixed-design/0208.-implement-trie-prefix-tree)***)***
{% endhint %}

We iterate through each word in the list to **insert the characters plus the symbol of the end of word #** into the Trie. Then, we traverse the Trie to get the longest common prefix.

* **If the length of the hash table in a certain node does equal to 1 or the symbol of the end of the word exists,** return the answer.
* Otherwise, we append the current char to the answer and move to the next node.&#x20;
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Trie:
    def __init__(self):
        self.root = {}
        
    def insert(self, word):
        curNode = self.root
        
        for char in word:
            if char not in curNode: curNode[char] = {}
            curNode = curNode[char]
            
        curNode['#'] = True
        
    def longestCommonPrefix(self):
        prefix  = ''
        curNode = self.root
        
        while True:
            if len(curNode) == 1 and '#' not in curNode: 
                curChar = list(curNode.keys())[0]
                prefix += curChar
                curNode = curNode[curChar]
            else: 
                return prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # (base case)
        if not strs: return ''
        if len(strs) == 1: return strs[0]
        
        # ==================================================
        #  Trie                                            =
        # ==================================================
        # time  : O(n), n = number of all characters in the array
        # space : O(n) 

        trie = Trie()
        for word in strs: trie.insert(word)
            
        return trie.longestCommonPrefix()
    
        '''
        # ==================================================
        #  Array + Sort                                    =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        strs.sort()
        
        shortStr = strs[0]
        longStr  = strs[-1]
        prefix   = ''
        
        for i in range(len(shortStr)):
            if shortStr[i] != longStr[i]: return prefix
            else: prefix += shortStr[i]
                
        return prefix
        
        # ==================================================
        #  Python Built-in Functions                       =
        # ==================================================
        os.path.commonprefix(strs)     
        '''
```

{% endtab %}
{% endtabs %}