Number of words = n, length of a word = m

Using the idea of trie-O(mn)-(4ms)

```
public class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
int shortest = Integer.MAX_VALUE;
for(String str : strs) shortest = Math.min(shortest, str.length());
int answer = shortest;
for(String str : strs){
int maxLen = 0;
for(int i = 0; i < shortest; i++){
if(str.charAt(i) == strs[0].charAt(i)){
maxLen++;
} else break;
}
answer = Math.min(answer, maxLen);
}
return strs[0].substring(0, answer);
}
}
```

Binary search based solution-1ms-O(nmlog(m))

```
public class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
int shortest = Integer.MAX_VALUE, answer = 0;
for(String str : strs) shortest = Math.min(shortest, str.length());
int low = 0, high = shortest;
while(low <= high){
int middle = (low + high) / 2;
if(isSubstring(strs, middle)) low = middle + 1;
else high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);
}
private boolean isSubstring(String[] strs, int length){
String match = strs[0].substring(0, length);
for(String str : strs) if(!str.substring(0, length).equals(match)) return false;
return true;
}
}
```