# LeetCode #14: Longest Common Prefix

Hello, coding enthusiasts! Today, we’re solving the “Longest Common Prefix” problem from LeetCode using Python and JavaScript.

## Problem Statement

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.

## Analysis

The problem is straightforward. We need to find the longest common prefix among all the strings. The prefix is a sequence of characters at the beginning of each string.

## Approach

Here’s a step-by-step approach to solve this problem:

1. Initialize Prefix: We start with the prefix as the first string in the array.
2. Iterate Over Strings: We iterate over each string in the array, starting from the second string.
3. Check Prefix: We check if the current string starts with the prefix. If it doesn’t, we remove the last character from the prefix.
4. Update Prefix: We continue removing the last character from the prefix until the current string starts with the prefix. If the prefix becomes an empty string, we return it.
5. Return Prefix: After iterating over all the strings, the prefix will be the longest common prefix. We return this prefix as the result.

## Time Complexity

The time complexity of this approach is `O(n*m)`, where n is the number of strings and m is the length of the largest string. This is because in the worst case, we are comparing m characters n times.

## Space Complexity

The space complexity is `O(1)`, because we are not using any additional space that scales with the input size.

## Code

### Python

Python
``````class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ''
shortest_str = min(strs, key=len)
for i, char in enumerate(shortest_str):
for other in strs:
if other[i] != char:
return shortest_str[:i]
return shortest_str``````

### JavaScript

JavaScript
``````var longestCommonPrefix = function(strs) {
if (!strs.length) return '';
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.substring(0, prefix.length - 1);
if (!prefix.length) return '';
}
}
return prefix;
};``````

## Conclusion

In conclusion, the “Longest Common Prefix” problem is a great example of how we can apply simple string manipulation techniques to solve problems in computer science.

The solution has a time complexity of `O(n*m)` and a space complexity of `O(1)`, making it highly efficient.

Happy coding!