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 the 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 to the corresponding character in all other strings.
4. Check for Mismatch: If a mismatch is found (a character doesn't match in one of the other strings), stop iterating and return the prefix found so far.
5. Return the Prefix: If the loop completes without finding a mismatch, the entire shortest string is the longest common prefix. Return the shortest string.

Explanation:

The algorithm efficiently finds the longest common prefix by comparing characters sequentially. It leverages the fact that the longest common prefix cannot exceed the length of the shortest string. By iterating through the shortest string and comparing characters, it avoids unnecessary comparisons. The moment a mismatch is encountered, the algorithm terminates, ensuring optimal performance.

Code:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        String shortestStr = strs[0];
        for (String str : strs) {
            if (str.length() < shortestStr.length()) {
                shortestStr = str;
            }
        }

        for (int i = 0; i < shortestStr.length(); i++) {
            char c = shortestStr.charAt(i);
            for (String str : strs) {
                if (str.charAt(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 with all other strings.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. The space used is independent of the input size.