Accepted c++ 6 lines 4ms


  • 37
    H
    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            string prefix = "";
            for(int idx=0; strs.size()>0; prefix+=strs[0][idx], idx++)
                for(int i=0; i<strs.size(); i++)
                    if(idx >= strs[i].size() ||(i > 0 && strs[i][idx] != strs[i-1][idx]))
                        return prefix;
            return prefix;
        }
    };

  • 0
    C

    Very nice solution~


  • 0
    Y
    This post is deleted!

  • 0
    Y

    class Solution {
    public:

    string longestCommonPrefix(vector<string>& strs) {
    	if (strs.empty()) return "";
    	string str1 = strs[0];
    	if (str1 == "") return "";
    
    	for (int i = 1; i < strs.size(); ++i) {
    		string str2 = strs[i];
    		if (str2 == "") return "";
    
    		int ind = 0;
    		while (str1[ind] == str2[ind]) ind++;
    		str1 = str1.substr(0, ind);
    	}
    
    	return str1;
    }
    

    };


  • 14

    Your code logic is a bit messy ......

    Here is the version I change a little, hope can help you ....

    You should make your code more readable ...

    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            string prefix="";
            if(strs.size()==0)  return prefix;
            
            /** check char by char, for each char, check all the string word **/
            for(int k=0; k<strs[0].size(); k++){
                int i=1;
                for(; i<strs.size() && strs[i].size()>k; i++){
                    if(strs[i][k]!=strs[0][k])
                        return prefix;
                }
                if(i==strs.size()) prefix+=strs[0][k];
            }
            return prefix;
        }
    };

  • 0
    M

    You're right.


  • 1
    L

    @RainbowSecret you don't have to check if i is equal to strs.size(). If i isn't equal to strs.size(), it will return prefix and quit this function


  • 0

    @lkwangpy if you dont check i, {aa, a} will results 'aa' being returned.


  • 2

    @RainbowSecret
    Nice solution, the only part I question is your prefix += strs[0][idx], because that is a string operation which will create a new string. Here is a 6 liner that is the most optimal I can think of

    • start at index 0
    • check each string if they have the same char at the index
    • if all have the same char increment the index
    • terminate if any mismatch is found or any string has exceeded it's length
    • also, avoids any string functions, adding strings, sub string, etc (except in my return)

    This seems like it will terminate the quickest, as soon as any string runs out or any character is not a match. It will do no unnecessary compares.

        public string LongestCommonPrefix(string[] strs) 
        {
            int min = 0;
            while (strs.Length > 0)
            {
                foreach (string s in strs)
                {
                    if (s.Length == min || s[min] != strs[0][min]) return strs[0].Substring(0, min);
                }
                min++;
            }
            return "";
        }
    

  • 0
    P

    I think this method can understand easier,first sort all the string object,then compared char by char
    class Solution {
    public:
    string longestCommonPrefix(vector<string>& strs) {
    string prefix = "";
    if(strs.size()==0 || strs[0] =="")
    return prefix;
    sort(strs.begin(),strs.end());
    if (strs[0] == "")
    return prefix;
    for(int i=0;i<strs[0].size();i++)
    {
    string temp_prefix = prefix;
    for(int j=1;j<strs.size();j++)
    {
    if (strs[0][i] != strs[j][i])
    return prefix;
    }
    prefix += strs[0][i];
    }
    return prefix;
    }
    };


Log in to reply
 

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