Given an array, arr[] of "n" different strings, the task is to find the longest common prefix among all strings present in the array.
Input: {"cup", "cupboard", "cut", "curse"}, Output: "cu"
Input: {"hit", "duper", "super"}, Output: "-1"
Solutions
Method 1: In O(n * length of prefix) time and O(1) space
The idea is to first calculate the length of shortest string, because the common prefix can not exceed the length of shortest string.
Next, start a loop from "0" to "length of shortest string", and in each iteration check if the ith character is same in each string.
If ith character is same in each string, than this character will be part of common prefix.
Else if in any iteration the ith character is different for any string, return substring of any string from 0 to i.
Complexity
The time complexity of this solution is O(n * length of prefix) and space complexity is O(N).