:orphan:

Longest Common Prefix
=====================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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: strs = ["flower","flow","flight"]
   Output: "fl"

**Example 2:**

::


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

 

**Constraints:**

- ``1 <= strs.length <= 200``
- ``0 <= strs[i].length <= 200``
- ``strs[i]`` consists of only lowercase English letters if it is
  non-empty.

.. highlight:: python

Pattern
-------
Array, String, Trie

Solution
--------
Iterate through each character in the shortest string and check if it is in all
other strings in ``strs``.

Code
----

.. literalinclude:: ../problems/easy/longest-common-prefix/longest_common_prefix__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from longest_common_prefix__approach_1 import longestCommonPrefix
>>> longestCommonPrefix(['flower', 'flow', 'flight'])
'fl'
>>> longestCommonPrefix(['dog', 'racecar', 'car'])
''

Complexity
----------
| :math:`n` is the number of strings in the input list and :math:`m` is the length of the shortest string
| Time: :math:`O(n m)` — :math:`n` strings, :math:`m` prefix length
| Auxiliary Space: :math:`O(1)`

.. autofunction:: longest_common_prefix__approach_1.longestCommonPrefix