Longest Common Prefix

Day 3, having completed the first two successfully, I was excited to take on the third one. Longest common prefix, given a list of strings, return the longest common prefix, otherwise return an empty string.

Problem Description

Thought Process

To solve this problem, I began by considering the simplest strategy: comparing characters across all strings one by one, starting from the first character. I chose the first string as a reference and iterated through each of its characters, checking if the same character exists at the same position in all other strings. If a mismatch is found or a string is shorter than the current position, I return the substring up to that point as the longest common prefix. I figured this would for one, avoid unnecessary comparisons once a mismatch is detected.

Get Arthur Pundo’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

My code

String longestCommonPrefix(List<String> strs) {

  // handle empty list
  if (strs.isEmpty) return "";

  // iterate over list using first string as reference
  for (int i = 0; i < strs[0].length; i++) {
    // get first character of the first string
    String char = strs[0][i];
    
    // compare the character with the same position in all other strings
    for (int j = 1; j < strs.length; j++) {
      // if we reach end or char mismatch occurs
      if (i >= strs[j].length || strs[j][i] != char) {
        // return the substring from the beginning to i
        return strs[0].substring(0, i);
      }
    }
  }
  // if no mismatches then the first string is the common prefix
  return strs[0];   
  }

This executed pretty well and fast, almost in the top 1 percentile. However, full disclosure, I got assistance from a colleague on how to go about it. My initial implementation did not pass every test case.

Conclusion

This was not at all simple. Took me a while to wrap my head around the concept and come up with a viable solution. This problem looks into the importance of understanding string traversal and early exit conditions for optimisation. Additionally, it shows how systematic comparison can be used when solving problems. I'm very excited for having completed this problem, looking forward to the next one.