题解 | #最长公共前缀#

#include <string>
class Solution {
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if(strs.size() == 0)
            return "";
        for(int i = 0;i<strs[0].size();++i)
        {
            char temp = strs[0][i];
            for(int j = 1;j<strs.size();++j)
            {
                if( i == strs[j].size() || strs[j][i] != temp)
                    return strs[0].substr(0,i);
            }
        }
        return strs[0];
    }
};

方法：遍历查找(推荐使用)

思路：

既然是公共前缀，那我们可以用一个字符串与其他字符串进行比较，从第一个字符开始，逐位比较，找到最长公共子串。

具体做法：

• step 1：处理数组为空的特殊情况。
• step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
• step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
• step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。