Sorted the array, Java solution, 2 ms


  • 73
    C

    Sort the array first, and then you can simply compare the first and last elements in the sorted array.

        public String longestCommonPrefix(String[] strs) {
            StringBuilder result = new StringBuilder();
            
            if (strs!= null && strs.length > 0){
            
                Arrays.sort(strs);
                
                char [] a = strs[0].toCharArray();
                char [] b = strs[strs.length-1].toCharArray();
                
                for (int i = 0; i < a.length; i ++){
                    if (b.length > i && b[i] == a[i]){
                        result.append(b[i]);
                    }
                    else {
                        return result.toString();
                    }
                }
            return result.toString();
        }

  • 0
    N
    This post is deleted!

  • 0
    X

    easy understand!!!


  • 10
    L
    This post is deleted!

  • 0
    X

    following is my AC code with 2ms;

    import java.util.Arrays;
    public class LongestCommonPrefix_14{
    public static void main(String[] args){
    String[] st = {"" , " " , " "};
    res = longestCommonPrefix_sort(st);
    System.out.println(res);
    }

    public static String longestCommonPrefix_sort(String[] strs) {
    	StringBuilder sb = new StringBuilder();
    	if(strs == null || strs.length == 0) 
    		return sb.toString();
    	
    	Arrays.sort(strs);
    	char[] start = strs[0].toCharArray();
    	
    	char[] end = strs[strs.length - 1].toCharArray();
    	
    	int j = 0;
    	int m = Math.min(start.length , end.length);
    	if(start.length == 0){
    		return sb.toString();
    	}else if( start[j] == end[j]){
    		sb.append(start[j]);
    		j++;
    		while(j < m ){
    			if(start[j] == end[j]){
    					sb.append(start[j]);
    					j++;
    			}else {
    				return sb.toString();
    			}
    		}			
    	}else{
    		return sb.toString();
    	}	
    	
    	return sb.toString();
    }
    

    }


  • 3
    W

    Could anyone tell me why we only need to compare the first and last one after sorting this array?


  • 1
    T

    You could also hash the characters in the string and then extract the min/max depending on the hash code. It is slightly more efficient than sorting all strings.


  • 0
    B

    you forget the sort.


  • 0
    J

    After sort, s2 is the last one~ thus it is still works in this test case


  • 1
    S

    Sort is O(nlogn), where n is the number of items to sort. But with strings, how does the string length factor into the complexity?


  • 8
    A

    @sean46

    Comparison between two strings are O(k) k is the length of two strings

    so the complexity of this algorithm is O(nlogn * k)

    It's slower than other solutions, other solutions don't require sorting and they are mostly O(n * k) complexity


  • 10
    K

    @LinnaYin When we sort a Strings array, we don't primarily sort by length so when the input that you've mentioned is sorted, the output will be -
    ["abd", "abdggg", "acfn"]


  • 0
    K

    @ArchiiiTech It does not sort every time while comparing two strings. I think it is O(nlogn) + O(n) = O(nlogn). Isn't it?


  • 1
    A

    @kangsanl Let's look at bubble sort, there're N^2 comparison in total and we usually think comparison takes O(1) time, thus the complexity of bubble sort is O(N^2); There are N*logN comparison in total for quicksort/mergesort, if each comparison takes O(k), so the time complexity should be NlogN * k. If you use bubble sort to sort an array of strings, each string with length of k, the complexity would be N^2 * k .


  • 1
    M

    Could anyone explain how the Arrays.sort() works for str arrays?


  • 7
    K

    @mirocody The Arrays.sort() for string array will check character by character and then sort accordingly. For e.g. ABC, ABD, ACD, ABA, ACA will be first checked for first char then second and so on.
    So, the solution will be:
    ABA, ABC, ABD, ACA, ACD


  • 1
    M

    @krutarthjoshi18 Thank you for the response!


  • 3
    F

    Very Neat and easily understood code!
    But, is the time complexity O(knlogn) for this algorithm, where k is the average length of every word?
    I think there is a brute-force method: Starting from the first character, we check if the jth character is the same for every string. If it is, then we move on to the next character and do the same checking; otherwise, if not every jth character is the same, or j is larger than the length of any string, then we stop and return the current longest prefix. I think this method has a time complexity of O(kn), where k is the minimum length of all the strings.


  • 0
    D

    I came up with a little bit revised version of this solution.

    I used a cout number to keep track with the similar part of the first and the last String of sorted string list and loop thru each charactor by calling charAt(count). Kept increment count until there's different, and break at this time.

    returning value would be the the substring of the first String from 0 to the count.


  • 4
    E

    Clean and easy to understand.

    However, I would replace the for-if-else fork with just one for loop:

    public String longestCommonPrefix(String[] strs) {
            // Argument checks
            if (strs == null || strs.length == 0) return "";
            if (strs.length == 1) return strs[0];
            
            StringBuilder sb = new StringBuilder();
            Arrays.sort(strs);
            char[] first = strs[0].toCharArray();
            char[] last = strs[strs.length - 1].toCharArray();
            for (int i = 0, j = 0; i < first.length && j < last.length; i++, j++) {
                if (first[i] != last[j]) break;
                sb.append(first[i]);
            }
            return sb.toString();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.