current position:Home>Longest common prefix, binary search problem

Longest common prefix, binary search problem

2022-02-02 23:20:46 CSDN Q & A

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[0].substr(0, low);
}

bool isCommonPrefix(const vector<string>& strs, int length) {    string str0 = strs[0].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:

copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.primo.wiki/2022/02/202202022320449281.html

Random recommended