题目描述

Longest Common Prefix

写一个函数，找到数组中各个字符串的最长相同前缀。 如果没有相同的前缀，返回 "" 。 所有的输入字符串组成都是 a-z 的小写字符

示例1：

Input: ["flower","flow","flight"]
Output: "fl"

示例2：

Input: ["dog","racecar","car"]
Output: ""
Explanation: 不存在相同前缀

javascript:

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function(strs) {

}

From leetcode No.14 Easy (opens new window)

解法

点击查看

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function(arr) {
	const len = arr.length;
	if(len === 0){
		return ""
	}
	if(len === 1){
		return arr[0]
	}
	const ret = []
	let i =0;
	while(i < arr[0].length){
		const s = arr[0][i]
		for(let j=1; j<arr.length; j++){
			if(arr[j].length <= i || arr[j][i] !== s){
				return ret.join("");
			}
		}
		ret.push(s)
		i++;
	}
	return ret.join("");
}

总结

一开始的思路是找出长度最短的元素，以他为参照，编写循环对比其它元素。　　 实际写的时候觉得以第一个元素为参照也行。 重点注意字符串数组长度为 0和 1的特殊情况。

照例学习他人的写法，比较巧妙地利用了字符串比较的特性来排序，排序后的字符串数组有规律可寻。

点击查看

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  if (strs.length === 0) {
    return '';
  } else if (strs.length === 1) {
    return strs[0];
  } else {
    let lcp = '';
    strs.sort((a,b) => a > b ? 1 : -1);
    const firstStr = strs[0];
    const lastStr = strs[strs.length - 1];
    for (let i = 0; i < firstStr.length; i++) {
      firstStr[i] === lastStr[i]
        ? lcp += firstStr[i]
        : i = firstStr.length;
    }
    return lcp;
  }
};