LetCode刷题[简单题](3)检测最长公共字符串（排序的妙用）

解决的问题是字符串最小的公共部分。

class Solution {
 
public:
 
    string longestCommonPrefix(vector& strs) {
 
    if (strs.empty()) {
 
        return "";  //如果是空字符串
 
    }
 
 
 
    // 对字符串数组按字典序排序
 
    std::sort(strs.begin(), strs.end());
 
 
 
    std::string prefix = "";
 
    int minLength = std::min(strs[0].length(), strs.back().length()); //最小的字符串长度，两端的字符串
 
 
 
    // 比较排序后的第一个字符串和最后一个字符串
 
    for (int i = 0; i < minLength; i++) {
 
        if (strs[0][i] == strs.back()[i]) {
 
            prefix += strs[0][i];
 
        } else {
 
            break;
 
        }
 
    }
 
 
 
    return prefix;
 
 
 
    }
 
};

问题转化技巧，字符串的公共头部的检测。

1. 朴素的逻辑理解方式是，直接暴力匹配比较所有的字符串知道有不同的部分

2. 功能重合思路转化，在C++中有一些相似功能实际已经做了相同字符串的排序，比如sort（），分类字符串的时候相同的公共部分已经做过排序判断排序，将相同的字符串聚集在一堆并且有着先后顺序的一堆，此时最不相似的字符串肯定已经分离开了，分离开的相似性最小的字符串就是两边的字符串，只需要针对两边的字符串进行判断公共部分就可以，最不像的字符串具有前缀的一票否决权，到否定的地方就可以得到所有前缀。