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


  • 0
    V

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

  • 0
    A

    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.


  • 0
    V

    @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) :)


  • 0
    A

    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


Log in to reply
 

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