Optimized sorting solution (Java)


  • 0
    A
    public String longestCommonPrefix(String[] strs) {
            if (strs.length == 0) { 
                return "";
            }
            
            String min = strs[0];
            String max = strs[0];
            for (String current : strs) {
                if (current.compareTo(max) > 0) {
                    max = current;
                } else if (current.compareTo(min) < 0) {
                    min = current;
                }
            }
            
            int num = 0;
            for (int i = 0; i < min.length() && i < max.length(); i++) {
                if (min.charAt(i) != max.charAt(i)) {
                    break;
                }
                num++;
            }
            return min.substring(0, num);
        }
    

    Explanation:
    You don't need sorting at all. All you need is the first and the last strings in sorted array. You can get them by finding min and max


  • -1

    What is your n?


  • 0
    A

    The number of strings.
    Basically it's O(n + k), where k is the number of chars in the longest prefix.


  • -1

    @alexilyenko O(n) and O(n+k) aren't the same. And neither is correct, as finding the min and max strings generally costs more. You seem to think that compareTo is O(1). It is not.


  • 0
    A

    @StefanPochmann well, we're talking about sorting solution. Mine is optimized version of that one.

    While sorting compareTo will be invoked internally anyway. Of course its time complexity depends on the lengths of the strings, their inequality etc, but you could say exactly the same thing about sorting and argue about its O(nlogn).


  • -1

    @alexilyenko said in O(n) solution (optimized sorting one):

    Of course its time complexity depends on the lengths of the strings, their inequality etc

    If you're aware of that, why are you still calling it O(number of strings)?

    but you could say exactly the same thing about sorting and argue about its O(nlogn).

    Who says that's O(nlogn)?


  • 0
    A

    @StefanPochmann I got your point. Yes, the worst case's complexity is O(2*(complexity of compareTo)*n + k),

    But neglecting all those things on large amount of data is a common approach, isn't it?


  • 0

    @alexilyenko The "2*" is useless, but why would any of the rest be neglected? I don't think that's common or reasonable.


  • 0
    A

    @StefanPochmann said in O(n) solution (optimized sorting one):

    @alexilyenko The "2*" is useless, but why would any of the rest be neglected? I don't think that's common or reasonable.

    Got it, thanks! Removed the time complexity so no one would be confused.


Log in to reply
 

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