How hard is LeetCode 14. Longest Common Prefix?

LeetCode 14. Longest Common Prefix is rated Easy on LeetCode.

What is the time complexity of LeetCode 14. Longest Common Prefix?

The Python solution on this page runs in O(n \times m), where n and m are the length of the string array and the minimum length of the strings, respectively.

What is the space complexity of LeetCode 14. Longest Common Prefix?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 14. Longest Common Prefix cover?

LeetCode 14. Longest Common Prefix is tagged Trie, Array and String on LeetCode.

Longest Common Prefix — LeetCode 14 Python Solution

EasyTrieArrayString

Problem: #14
Pattern: Trie
Reading time: 2 min
Source: leetcode.com

The problem

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

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

Python solution

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs[1:]:
                if len(s) <= i or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]

Complexity

Measure	Complexity
Time	O(n \times m), where n and m are the length of the string array and the minimum length of the strings, respectively
Space	O(1) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 14. Longest Common Prefix is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

On a study list

This problem is on Top Interview 150.

Frequently asked questions

How hard is LeetCode 14. Longest Common Prefix?: LeetCode 14. Longest Common Prefix is rated Easy on LeetCode.
What is the time complexity of LeetCode 14. Longest Common Prefix?: The Python solution on this page runs in O(n \times m), where n and m are the length of the string array and the minimum length of the strings, respectively.
What is the space complexity of LeetCode 14. Longest Common Prefix?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 14. Longest Common Prefix cover?: LeetCode 14. Longest Common Prefix is tagged Trie, Array and String on LeetCode.