# Longest common prefix, binary search problem

2022-02-02 23:20:46

class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (!strs.size()) {
return "";
}
int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();
int low = 0, high = minLength;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
}
else {
high = mid - 1;
}
}
return strs.substr(0, low);
}

``bool isCommonPrefix(const vector<string>& strs, int length) {    string str0 = strs.substr(0, length);    int count = strs.size();    for (int i = 1; i < count; ++i) {        string str = strs[i];        for (int j = 0; j < length; ++j) {            if (str0[j] != str[j]) {                return false;            }        }    }    return true;}``

};
ask ：int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size(); I can't understand this code , I hope to be a responsible boss , Help me analyze them one by one , I don't understand the grammar of this [](const string& s, const string& t)
ask ：bool isCommonPrefix The end of this function return true, I'm so confused , Isn't it that every call to this function will return true Do you , If not why
A responsible big man

Refer to the answer 1：
1. min_element Returns the minimum value in the container , Default string Compare compare... Based on string "a" < "b"
Defined here [](const string& s, const string& t) {return s.size() < t.size();} yes c++ Lambda function , Compare string length
therefore , The shortest string is returned here
then int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size(); Or get minLength The shortest string length in the string container

2. bool isCommonPrefix This function is to determine the first... In the string array length Are they the same? , See if there are different returns in the implementation false. If the cyclic comparisons are the same , The function finally returns true.

Refer to the answer 2：

Refer to the answer 3：

Function , The first 8 That's ok ,return after , The whole is directly interrupted and returned , No subsequent code will be executed , End directly .

Refer to the answer 4：