This problem is taken from 14. Longest Common Prefix .

Approach 1

Take the first string (say first) of the array and assume it to be the longest prefix. Then compare it with other strings one at a time and keep track of the length of the longest prefix. After comparing first string with all other string and having the length of the longest prefix, we simply return the substring first[0, longest_prefix_length].

This approach has time complexity O(n*m) and space complexity as O(1), where n is the length of array and m is the length of the longest string.

// Java code to find Longest Common Prefix
class Solution {
    public String longestCommonPrefix(String[] strs) {
        String pre = strs[0];
        int max_pre_len = pre.length();

        for(int i=1; i<strs.length; i++) {
            // check only upto max. pre_len
            max_pre_len = max_pre_len < strs[i].length() ? max_pre_len : strs[i].length();

            // compare two strings
            int curr_len = 0;
            for(int j=0; j<max_pre_len; j++) {
                if(pre.charAt(j) == strs[i].charAt(j)) 
                    curr_len++;
                else 
                    break;
            }

            // make curr. pre length to max. pre length
            max_pre_len = curr_len;
        }

        return pre.substring(0, max_pre_len);
    }
}

Approach 2

We sort the array of strings and compare the first and last string of the array to find the length of the longest prefix. And then we return the substring as in Approach 1.

// Java code to find Longest Common Prefix
class Solution {
    public String longestCommonPrefix(String[] strs) {
        // sort the array
        Arrays.sort(strs);

        char[] a = strs[0].toCharArray();
        char[] b = strs[strs.length - 1].toCharArray();

        int n = Math.min(a.length, b.length);
        int pre_len = 0;

        for(int i=0; i<n; i++) {
            if(a[i] == b[i])    
                pre_len++;
            else
                break;
        }

        return strs[0].substring(0, pre_len);
    }
}

This approach has time complexity of O(log(n) + (n * m)) and space complexity of O(n), used internally to sort the array.