Longest Common Prefix easy

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.

Steps

1. Handle Empty Input: If the input array strs is empty or null, return an empty string "".
2. Find Shortest String: Determine the shortest string in the array. The longest common prefix cannot be longer than the shortest string.
3. Iterate and Compare: Iterate through the characters of the shortest string. For each character, compare it with the corresponding character in all other strings in the array.
4. Mismatch Handling: If a mismatch is found (a character at a given index differs between the shortest string and any other string), stop the iteration and return the prefix found so far.
5. Return Prefix: If the iteration completes without finding any mismatches, the entire shortest string is the longest common prefix, so return it.

Explanation

The algorithm efficiently finds the longest common prefix by focusing only on the shortest string. This is because the longest common prefix cannot exceed the length of the shortest string. By iterating character by character and comparing against all other strings, we avoid unnecessary comparisons. The algorithm stops as soon as a mismatch is detected, preventing further unnecessary computation.

Code

using System;

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) {
            return "";
        }

        string shortestStr = strs[0];
        foreach (string str in strs) {
            if (str.Length < shortestStr.Length) {
                shortestStr = str;
            }
        }

        for (int i = 0; i < shortestStr.Length; i++) {
            char c = shortestStr[i];
            foreach (string str in strs) {
                if (str[i] != c) {
                    return shortestStr.Substring(0, i);
                }
            }
        }

        return shortestStr;
    }
}

Complexity

• Time Complexity: O(S * N), where N is the number of strings and S is the length of the shortest string. In the worst case, we might need to compare all characters of the shortest string against all other strings.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We're not creating any large data structures proportional to the input.