Longest common prefix for set of strings

Question

Question: Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example :

Input: strs = ["flower","flow","flight"]
Output: "fl"

Source: https://leetcode.com/problems/longest-common-prefix/

My Code:

public String longestCommonPrefix(String[] strs) {
        StringBuilder lcp = new StringBuilder();

        
        //compute min length 
        int minLength = Integer.MAX_VALUE;
        for(String str:strs){
            
            if (str.length() < minLength) {
                minLength = str.length();
            }
            
        }
            
        for (int i = 0; i < minLength;i++){
            char cmp = strs[0].charAt(i);
        for(String str:strs){
            
            if (str.charAt(i) != cmp) {
                return lcp.toString();
             }
            
           }
          lcp.append(cmp);
        }
        
        return lcp.toString();
    }

Questions:

1. Current time complexity is O(mn) where n is number of strings and m is the min string length. Can it be faster?
2. How to improve code style in general.

Answer 1

1. Don't think too much about performance.

Worst performance problems arise because the coder thought something could be faster but she didn't consider that the JVM does runtime optimizations for her code.

So always prefer writing readable code that works. Only step into performance optimization if you actually faced a performance issue and you have proven by measurement that this particular piece of code is the problem and the alternative approach really solves the problem.

2. Why are you inventing the wheel a 4th time?

The JVM has methods to compare strings. There is even a startsWith() method that would perfectly fit.

3 Structure your code

Your code has 2 obvious parts. The first one you marked with an inline comment.

Better use methods with good names for this kind of structuring.

An alternative solution could look like this:

My solution made some assumption on the behavior of the methods in the String class which I verified with spikes coded as JUnit Tests along with the acceptance test using your given example.

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

class LongestCommonPrefixTest {

    @Test
    void spike__does_StartsWith_returnTrueForTheEmptyString() {
        assertTrue("someWord".startsWith(""));
    }

    @Test
    void spike__does_substring_returnTheEmptyStringForEndIndexZero() {
        assertEquals("", "someWord".substring(0, 0));
    }

    @Test
    void spike__does_substring_returnShorterStringForLengthMinus1() {
        String someWord = "someWord";
        assertEquals("someWor", someWord.substring(0, someWord.length() - 1));
    }

    @Test
    void acceptanceTest() throws Exception {
        String[] strs = { "flower", "flow", "flight" };
        String longestCommonPrefix = //
                new LongestCommonPrefix().longestCommonPrefix(strs);
        assertEquals("fl", longestCommonPrefix);
    }

}

And this is the solution I came up with:

public class LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        String currentPrefix = selectFirstWordOrEmptyString(strs);
        for (String currentWord : strs) {
            currentPrefix = findCommonPrefixIn(currentPrefix, currentWord);
        }
        return currentPrefix;
    }

    private String selectFirstWordOrEmptyString(String[] strs) {
        return 0 == strs.length ? "" : strs[0];
    }

    private String findCommonPrefixIn(String currentPrefix, String currentWord) {
        while (!currentWord.startsWith(currentPrefix)) {
            currentPrefix = currentPrefix.substring(0, currentPrefix.length() - 1);
        }
        return currentPrefix;
    }
}

A performance improvement could be possible if you always pass the shorter of currentPattern and currentWord as first parameter to the private method and the longer one as second. But as I wrote you shouldn't do that unless necessary.

Answer 2

1. Can it be faster?

I don't think there is an approach with a better complexity, but the runtime can be improved.

Finding the shortest string can be avoided by adding one more condition in the for-loop:

public String longestCommonPrefix(String[] strs) {
    StringBuilder lcp = new StringBuilder();
    for (int i = 0; i < strs[0].length(); i++){
        char cmp = strs[0].charAt(i);
        for(String str: strs){
            if (i == str.length() || str.charAt(i) != cmp) {
                return lcp.toString();
            }
        }
        lcp.append(cmp);
    }
    return lcp.toString();        
}

The condition i == str.length() returns as soon as the shortest string is consumed.

I doubt that Leetcode is able to spot the difference in runtime but in theory, it should be faster. As @TimothyTruckle points out in the comments, better to measure it and see whether there is an actual improvement.

---

2. How to improve code style in general.

My suggestion is to format the code properly. There are some problems (medium and hard) that take more than few lines of code and can get quite messy without properly formatting the code.

Unfortunately, Leetcode does not provide a built-in auto-formatting (as far as I know), but there are websites to help with it.

Finding the length of the shortest string

int minLength = Integer.MAX_VALUE;
for(String str:strs){
    if (str.length() < minLength) {
        minLength = str.length();
    }
}

This is an alternative using Streams:

int minLength = Arrays.stream(strs)
        .min(Comparator.comparingInt(String::length))
        .get().length();

Answer 3

Is it fast enough?

Then don't worry about it.

If you don't truly know, measure.

Otherwise, remember that locality counts, so finish processing each string in one go, if you can.

Finding the minimal length can reduce the worst case. But does it really matter for you?

Extract functions

Suddenly, you no longer need comments. And the result is more flexible, and solves more problems.

public int minLength(String[] strs) {
    int r = Integer.MAX_VALUE;
    for (String s : strs)
        r = Math.min(r, s.length());
    return r;
}

public String maxPrefixCapped(String[] strs, int n) {
    if (strs.length == 0) return "";
    String x = strs[strs.length - 1];
    for (String s : strs) {
        int m = n;
        for (n = 0; n < m && s.charAt(n) == x.charAt(n); ++n)
            /* */;
    }
    return x.substring(0, n);
}

public String maxPrefix(String[] strs) {
    return maxPrefixCapped(strs, minLength(strs));
}