Question 14

Longest Common Prefix

The Longest Common Prefix (LCP) problem involves finding the longest prefix that is common to all the strings in a given array of strings. The horizontal scanning approach is one of the simplest ways to solve this.

Approach: Horizontal Scanning

1. Start by assuming the first string in the list is the longest common prefix.
2. Compare the assumed prefix with the next string in the list.
3. Shorten the prefix by removing characters from the end until it matches the current string.
4. If at any point the prefix becomes an empty string, return an empty string as the result.
5. Continue comparing the prefix with the rest of the strings until all strings have been processed.

Complexity:

Time Complexity: O(n), where n is the sum of the lengths of all strings in the input list.

Space Complexity: O(1), as the solution uses constant space, excluding the input and output.

Java Code Implementation:

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

        // Start with the first string as the initial prefix
        String prefix = strs[0];

        // Compare the prefix with each string in the array
        for (int i = 1; i < strs.length; i++) {
            // While the prefix is not a prefix of the current string, shorten it
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix;
    }

    public static void main(String[] args) {
        LongestCommonPrefix solution = new LongestCommonPrefix();
        String[] strs = {"flower", "flow", "flight"};
        System.out.println(solution.longestCommonPrefix(strs));  // Output: "fl"
    }
}