题解 | #最长公共前缀#

二维遍历纵向查找

有字符串数组["abca","abc","abca","abc","abcc"]，将它的子字符串想象成如下图的结构，每一行是字符串数组的元素，每一列是要比较的字符。当我们求公共前缀时，可以用任意一个子字符串与其他子字符串比较，从第一个字符开始，逐位比较，即可找最长公共前缀。

代码实现

function longestCommonPrefix( strs ) {
    if(!strs.length) {
        return '';
    }
    
    let maxLenFrontStr = '';
	// 基准子字符串strs[0]
    for (let i = 0; i < strs[0].length; i++) {
        let j = 0;
      // 其他子字符串与strs[0]进行逐位比较
        while (j < strs.length - 1) {
            if (strs[j][i] === strs[ j + 1][i]) {
                j++
            } else {
                return maxLenFrontStr;
            }
        }
        maxLenFrontStr += strs[0][i];
    }
    // 若字符串数组的长度为1，则直接返回第一个子字符串。
    return strs[0];
}

时间复杂度为：O(mn)，m为最长公共前缀字符串的长度。

空间复杂度为：O(1)