Practice/Meta/Leetcode 14. Longest Common Prefix

Leetcode 14. Longest Common Prefix

CodingMust

Problem

Given an array of strings, find the longest string that is a common prefix shared by all strings in the array. If no common prefix exists, return an empty string.

A prefix is a substring that appears at the beginning of each string. For example, "pre" is a prefix of "prefix" and "prepare", but not of "suppose".

Requirements

1. Return the longest prefix that appears at the start of every string in the input array
2. If there is no common prefix among all strings, return an empty string ""
3. The comparison should be case-sensitive
4. Handle edge cases such as empty arrays or arrays with a single string

Constraints

• 0 ≤ words.length ≤ 200
• 0 ≤ words[i].length ≤ 200
• words[i] consists of only lowercase English letters
• Time complexity should be O(S) where S is the sum of all characters in all strings
• Space complexity should be O(1) excluding the output

Examples

Example 1:

Input: words = ["flower", "flow", "flight"] Output: "fl" Explanation: The prefix "fl" is common to all three words.

Example 2:

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

Example 3:

Input: words = ["interstellar", "internet", "interval"] Output: "inter" Explanation: All three words start with "inter".

Example 4:

Input: words = ["single"] Output: "single" Explanation: With only one word, the entire word is the common prefix.