Optimal Solution (?)


  • 10

    I think there are two (straightforward) solutions:

    1. "Horizontal matching (over strings)". Pick up the first string and compare it with the rest. Return the minimum prefix found among all comparisons.

    2. "Vertical matching (over characters)". Compare the characters between all strings from left to right. Stop whenever a mismatch is found.

    What is the complexity of these two approaches ?

    Is there a better solution ?


  • 45
    G

    The first one is apparently not very optimal. Imagine only the last string is different from all others. You would have wasted so much time comparing the previous ones.
    The second one is the optimal solution.
    The question is equivalent to: what is the fastest way to fail? It seems the second one is the only answer.

    The following is a possible solution using Java:

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
    		return "";
    	
    	for (int i = 0; i < strs[0].length() ; i++){
    		char c = strs[0].charAt(i);
    		for (int j = 1; j < strs.length; j ++) {
    			if (i == strs[j].length() || strs[j].charAt(i) != c)
    				return strs[0].substring(0, i);    			
    		}
    	}
    	return strs[0];
    }

  • -22
    J

    The second one is better. Time complexity is O(m), where m is the number of strings.


  • 0
    Y

    why so many downvoting, what he said is "almost" right. the complexity is O(min_string_length*num_of_strings)


  • 0
    E

    Use the first string as "result". This result can only be equal or shorter than this length. So we keep "cutting" this result.

    This might not be the fastest solution. Just provide another way of solving.

    public class Solution {
        public String longestCommonPrefix(String[] strs) {
            if (strs.length == 0) {
                return "";
            }
            StringBuilder sb = new StringBuilder(strs[0]);
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].length() < sb.length()) {
                    sb.delete(strs[i].length(), sb.length());
                }
                for (int j = sb.length() - 1; j >= 0; j--) {
                    if (sb.charAt(j) != strs[i].charAt(j)) {
                        sb.delete(j, sb.length());
                    }
                }
            }
            return sb.toString();
        }
    }

  • 0
    C
    This post is deleted!

Log in to reply
 

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