Strings - Longest Common Prefix

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 "".

Input: strs = ["flower","flow","flight"]
Output: "fl"
Explanation: longest common prefix among all strings is "fl".

Input: s = " fly me to the moon "
Output: 4
Explanation: The last word is "moon" with length 4.

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Solution 1 - check character by character from all strings in a vertical fashion

In this approach, we are going to start of with one of the string from strings array as base prefix, then compare each character from this base prefix to all other remaining strings from strings array in a vertical fashion, meaning that compare 1^st charcater in all strings, then 2^nd character and so on... as long as we did not go out of bounds on any string.

We will create a function checkCharsVertically that takes input argument strings strs.
Create a variable longest to keep track of longest prefix length found so far, and take the first element from strs array as base prefix.
Then, loop through all strings vertically, 1^st character in all strings and then 2^nd character and so on, when all strings have a character in common then increment longest variable, continue this until one of string have no matching character.
When a character match is not found in any string or at the end simply return substring from base prefix from 0 and longest indexes.

The reason why we return when a character mismatch found in string and at the end is because when strs have more than one string, we can return our answer right there. For example if the input strs array is ["flower","flow","flight","floss"], if you notice first two characters are a match in all strings "fl", then you see a break at 3^rd string and we can simply return at that step.
When input array has only one string, then it comes to return statement at the end.

public class LongestCommonPrefix { static String checkCharsVertically(String[] strs) { int longest = 0; String prefix = strs[0]; for(int i=0; i<prefix.length(); i++) { for(int j=1; j<strs.length; j++) { if(i == strs[j].length() || prefix.charAt(i) != strs[j].charAt(i)) { return prefix.substring(0, longest); } } longest++; } return prefix.substring(0, longest); } }

Complexity Analysis:

Time complexity: Above code runs in O(n * m) time where n is the input strings strs length and m is the minimum length string out of all strings.
Space complexity: O(m) for the prefix we are returning.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis: