Question 39 : Longest Common Prefix in an array of Strings in java

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example :

String[] strArr={"java2Tech","javaworld","javabean","javatemp"};
So Longest common prefix in above String array will be “java” as all above string

Java — Vertical Scan

public class LongestCommonPrefix {

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

        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);

            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

Python

def longest_common_prefix(strs):
    if not strs:
        return ""

    for i in range(len(strs[0])):
        c = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != c:
                return strs[0][:i]
    return strs[0]

 Horizontal Scanning (Compare Pairwise)

public static String longestCommonPrefixHorizontal(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

Python
def longest_common_prefix_horizontal(strs):
    if not strs:
        return ""

    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

 Divide & Conquer (Recursive)
public static String longestCommonPrefixDivide(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    return divide(strs, 0, strs.length - 1);
}

private static String divide(String[] strs, int l, int r) {
    if (l == r) return strs[l];
    int mid = (l + r) / 2;
    String leftPrefix = divide(strs, l, mid);
    String rightPrefix = divide(strs, mid + 1, r);
    return commonPrefix(leftPrefix, rightPrefix);
}

private static String commonPrefix(String left, String right) {
    int minLen = Math.min(left.length(), right.length());
    for (int i = 0; i < minLen; i++) {
        if (left.charAt(i) != right.charAt(i)) {
            return left.substring(0, i);
        }
    }
    return left.substring(0, minLen);
}

Python
def longest_common_prefix_dc(strs):

    def common_prefix(left, right):
        min_len = min(len(left), len(right))
        for i in range(min_len):
            if left[i] != right[i]:
                return left[:i]
        return left[:min_len]

    def divide(l, r):
        if l == r:
            return strs[l]
        mid = (l + r) // 2
        left_prefix = divide(l, mid)
        right_prefix = divide(mid + 1, r)
        return common_prefix(left_prefix, right_prefix)

    if not strs:
        return ""
    return divide(0, len(strs) - 1)




  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    
Vertical scanning
    
O(n × m)
    
O(1)
    
⭐ Best & simple
  

  

    
Horizontal scanning
    
O(n × m)
    
O(1)
    
✔ Good & readable
  

  

    
Divide & conquer
    
O(n × m)
    
O(log n)
    
✔ Recursive style