## Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

### Analysis:

Note that we have an array of strings, where we only need the common prefix, for all these strings.In other words, for each char in the strings (starts from [0] ), if they are the same, it is a common prefix, we continue check the next index (e.g., [1] ), if they are the same, we continue check the next (e.g., [2])... The termination conditions are: (1) one string ends, then the longest prefix is the string itself. (2) The chars of same index are not the same, the longest prefix is the sub string from 0 to current index-1.

So the algorithm is pretty simple, scan from the first character, if it is same for all the strings, go to the next character. Return the string until meet the different character.

### Code(C++):

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

### Code (Python):

class Solution: # @return a string def longestCommonPrefix(self, strs): if (len(strs)==0): return "" if (len(strs)==1): return strs[0] for j in xrange(0,len(strs[0])): for i in xrange(0,len(strs)-1): if (j>=len(strs[i+1]) or strs[i][j]!=strs[i+1][j]): if j==0: return "" else: return strs[i][0:j] return strs[0]

You don't require that extra boolean variable (f1) , if the condition (strs[j][i]!=str[i]) becomes true, you can just return str.substr(0, i) from there only. Otherwise, when the loop terminates without then at the end, you can just return the whole string str;

ReplyDeleteYes, it is a good suggestion ! I have modified the code (also add the python version).

DeleteThanks !

I would first sort the strings in alphabetical order. And only compare the first and last strings. Use bisection to accelerate

ReplyDelete