Longest Common Prefix

• Find minLen, the length of the shortest string in the array. The LCP cannot be longer than this.
• Initialize a search range for the length, low = 0, high = minLen.
• While low <= high:
  • Calculate the middle length mid = low + (high - low) / 2.
  • Check if a common prefix of length mid exists across all strings. To do this, take the prefix of the first string, strs[0].substring(0, mid), and verify if all other strings start with it.
  • If a common prefix of length mid exists, it means we might find an even longer one. We record mid as a potential answer and search in the right half: low = mid + 1.
  • If it does not exist, mid is too long. We must search for a shorter prefix in the left half: high = mid - 1.
• After the loop terminates, the last successfully recorded length corresponds to the longest common prefix. Return strs[0].substring(0, lastSuccessfulLength).

The core idea is to binary search for the length of the longest common prefix. We first determine the maximum possible length by finding the length of the shortest string in the array, let's call it minLen. Our search space for the length is then [0, minLen]. For each length k we test (picked by the binary search), we check if the first k characters are a common prefix for all strings in the array. If they are, we know the LCP is at least k characters long, so we try a larger length. If they are not, k is too large, and we must try a smaller length. We continue this process until the search space is exhausted, and the largest k that worked is our answer.

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        if (strs == null || strs.length == 0) {4            return "";5        }6        int minLen = Integer.MAX_VALUE;7        for (String str : strs) {8            minLen = Math.min(minLen, str.length());9        }10        int low = 0;11        int high = minLen;12        while (low <= high) {13            int middle = low + (high - low) / 2;14            if (isCommonPrefix(strs, middle)) {15                low = middle + 1;16            } else {17                high = middle - 1;18            }19        }20        return strs[0].substring(0, (low + high) / 2);21    }22 23    private boolean isCommonPrefix(String[] strs, int len) {24        if (len == 0) return true;25        String prefix = strs[0].substring(0, len);26        for (int i = 1; i < strs.length; i++) {27            if (!strs[i].startsWith(prefix)) {28                return false;29            }30        }31        return true;32    }33}

• Define a recursive function, say lcp(strs, left, right), that finds the LCP for the subarray strs[left...right].
• The base case for the recursion is when left == right. In this case, there is only one string, so the LCP is the string itself. Return strs[left].
• In the recursive step, divide the current array range into two halves by finding the middle index mid = (left + right) / 2.
• Make two recursive calls: one for the left half, lcpLeft = lcp(strs, left, mid), and one for the right half, lcpRight = lcp(strs, mid + 1, right).
• Once the results from both halves are returned, combine them by finding the common prefix of lcpLeft and lcpRight. This can be done with a helper function that compares two strings character by character.
• The result of this combination is the LCP for the range [left, right].

The logic behind this method is that LCP(S1, S2, ..., Sn) = LCP(LCP(S1, ..., Sk), LCP(Sk+1, ..., Sn)). We can split the array of strings into two halves, find the LCP for each half recursively, and then find the LCP of the two resulting strings. This process continues until we are left with subproblems of a single string, where the LCP is the string itself. The results are then merged back up the recursion tree.

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        if (strs == null || strs.length == 0) {4            return "";5        }6        return longestCommonPrefix(strs, 0, strs.length - 1);7    }8 9    private String longestCommonPrefix(String[] strs, int l, int r) {10        if (l == r) {11            return strs[l];12        } else {13            int mid = l + (r - l) / 2;14            String lcpLeft = longestCommonPrefix(strs, l, mid);15            String lcpRight = longestCommonPrefix(strs, mid + 1, r);16            return commonPrefix(lcpLeft, lcpRight);17        }18    }19 20    String commonPrefix(String left, String right) {21        int min = Math.min(left.length(), right.length());22        for (int i = 0; i < min; i++) {23            if (left.charAt(i) != right.charAt(i)) {24                return left.substring(0, i);25            }26        }27        return left.substring(0, min);28    }29}

• If the input array is empty or null, return an empty string "".
• Initialize a variable prefix with the first string of the array, strs[0].
• Iterate through the array from the second string (i = 1) to the end.
• For each string strs[i], check if it starts with the current prefix. A while loop with strs[i].indexOf(prefix) != 0 can be used for this.
• If strs[i] does not start with prefix, shorten the prefix by removing its last character: prefix = prefix.substring(0, prefix.length() - 1).
• Repeat this until prefix is a prefix of strs[i] or it becomes empty.
• If prefix becomes empty, it means there is no common prefix, so we can return "" immediately.
• After the outer loop finishes, the remaining prefix is the longest common prefix for all strings.

We begin by taking the first string as our initial guess for the longest common prefix. Then, we iterate through the remaining strings one by one. For each string, we compare it against our current prefix. If the string doesn't start with the prefix, we trim the last character from our prefix and check again. We continue this trimming process until the prefix is a valid prefix for the current string. If our prefix ever becomes an empty string, we know no common prefix exists and can stop early. After checking all the strings, whatever remains of our initial guess is the final answer.

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        if (strs == null || strs.length == 0) {4            return "";5        }6        String prefix = strs[0];7        for (int i = 1; i < strs.length; i++) {8            while (strs[i].indexOf(prefix) != 0) {9                prefix = prefix.substring(0, prefix.length() - 1);10                if (prefix.isEmpty()) {11                    return "";12                }13            }14        }15        return prefix;16    }17}

• If the input array is empty or null, return "".
• Iterate through the characters of the first string, strs[0], using an index i from 0 to strs[0].length() - 1.
• For each character c at index i in the first string:
  • Start an inner loop to iterate through all other strings in the array, from j = 1 to strs.length - 1.
  • In the inner loop, check for two mismatch conditions for the string strs[j]:
    1. The index i is out of bounds for strs[j] (i.e., i == strs[j].length()).
    2. The character at strs[j].charAt(i) is not equal to c.
  • If either condition is true, it means the common prefix ends at index i-1. Return the prefix found so far, which is strs[0].substring(0, i).
• If the outer loop completes without finding any mismatches, it means the entire first string is a common prefix. In this case, return strs[0].

The vertical scanning method is one of the most efficient ways to solve this problem. We iterate through the characters of the first string from left to right. For each character, we then scan down through all the other strings to ensure they have the same character at the same position. If we find any string that either doesn't have a character at that position or has a different character, we know the longest common prefix is the substring we've successfully matched up to that point. This allows for an early exit and avoids unnecessary comparisons, making it very fast in practice, especially when the common prefix is short.

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        if (strs == null || strs.length == 0) {4            return "";5        }6        for (int i = 0; i < strs[0].length(); i++) {7            char c = strs[0].charAt(i);8            for (int j = 1; j < strs.length; j++) {9                if (i == strs[j].length() || strs[j].charAt(i) != c) {10                    return strs[0].substring(0, i);11                }12            }13        }14        return strs[0];15    }16}