# Why here O(mn) solution is 4ms and O(mnlog(m)) is 1ms?

• 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;
}
}
}
}
``````

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;
}
}``````

• I dont think the complexity of the binary search method is nmlogm.

1. for loop to find shortest length = O(n)
2. while loop from 0 to shortest where binary search happens = O(logm)
3. isSubstring method takes O(n) times, but is called only O(logm) times

total is O(n) + O(logn)*O(n)= O(nlogm). Thus program runs faster.

• @aishwarya6 I think isSubstring method is O(n) * O(m) = O(nm) [ie to iterate in the for loop n times and m for substring matching) . Then isSubstring is called O(logm) times, so final complexty is O(logm) * O(nm) = O(nmlogm) :)

• time complexity of the string.substring() method depends on the java version. Since Java 7 Update 6, substring takes linear (O(n)) time, whereas before that it used to take constant time. Maybe this is causing the program to run faster.

http://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.