题目14. 寻找公共最长前缀
题目描述
要求： 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 `""`。
示例
输入：strs = ["flower","flow","flight"]
输出："fl"
思路1. 横向搜索
我们可以遍历字符串数组，字符串两两进行比较，找出其中的公共前缀，在比较过程中，公共前缀长度不会增加，只会保持不变或者递减，当变为0时，说明没有公共前缀，此时返回”“。若字符串数组长度为1，则直接返回第一个元素即可。
例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。
1. 比较flower和flow这两个字符串，找出公共前缀flow
2. 将上一次的公共前缀flow与flight进行比较，找出公共前缀fl
3. 将上一次的公共前缀fl与flat进行比较，找出公共前缀fl
4. 遍历结束，返回公共前缀fl
下面是JavaScript实现
/**
* 思路：
* 两两比较，找出最长的公共前缀，然后这个公共前缀和下一个词比较
* 只要公共前缀不为空，且没有到最后一个词，就继续比较，否则停止，并返回前缀
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
let commonPrefix = ''
let count = strs.length
let prefixPerTime = strs[0]
for (let i = 1; i < count; i++) {
let a = prefixPerTime
let b = strs[i]
prefixPerTime = findCommonPrefix(a, b)
if (prefixPerTime.length === 0) {
return ''
}
}
commonPrefix = prefixPerTime
return commonPrefix
}
/**
* 找出公共前缀
* @param {string} a
* @param {string} b
* @return {string}
*/
function findCommonPrefix(a, b) {
let len = Math.min(a.length, b.length)
let subStr = a.substring(0, len)
for (let i = 0; i < len; i++) {
if (a[i] !== b[i]) {
return a.substr(0, i)
}
}
return subStr.substring(0, len)
}
思路2 纵向搜索
我们可以将所有字符串纵向排列，从下标0开始遍历每个字符，假设索引为index，当我们发现index为某个值的时候，字符不唯一，则停止遍历，返回公共前缀。
例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。
1. 将所有字符串纵向排列，并用最短的字符串长度为基准，进行截断。
flow
flow
flig
flat
2.从左到右遍历每个字符，找到出现不同字符的那一列的下标index。
3.公共前缀就是下标从0到index-1的子串
下面是JavaScript实现
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
let count = strs.length
let commonPrefix = []
let len = strs[0].length
for(let i = 0 ; i < len ; i++) {
let c = strs[0][i]
for(let k = 1 ; k <count;k++) {
let c_ = strs[k][i]
if(c !== c_) {
return commonPrefix.join('')
}
}
commonPrefix.push(c)
}
return commonPrefix.join('')
}
思路3 二分搜索
同纵向搜索，我们首先也是将所有字符串纵向排列，不过在搜索最长公共前缀右边界的时候，可以不用依次遍历的方式，而采用二分搜索的方法。找到一个中心点，左侧如果字符串相同则右边界在右侧，反之在左侧。确定一侧后再次进行二分搜索，不断找下去，即可找到右边界。
例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。
统一字符串长度，即取最小的字符串的长度为统一长度（公共前缀长度必然小等于该值），此处minLen=4
-
将所有字符串按照统一长度截断后，纵向排列，即
['flow','flow','flig','flat'] 进行二分搜索，确定中心点
，并确定
验证字符串的子串
是否相同，此处都为
取
重新回到步骤3（若不相同则取
重新回到步骤3）
此时验证子串
发现不同，停止。
返回公共前缀，索引为
即
下面是JavaScript实现
/**
* 采用二分法找到最长公共前缀
* 1. 首先确定所有字符串的最小长度minLen
* 2. 在0~minLen区间上二分查找，如果0~mid相同，则前缀在mid右边，反之在左
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (strs == null || strs.length === 0) {
return ''
}
if (strs.length === 1) return strs[0]
let minLen = strs[0].length
for (let str of strs) {
minLen = Math.min(str.length, minLen)
}
// 进行二分查找
let low = 0,
high = minLen - 1
while (low <= high) {
let mid = Math.floor((high - low) / 2) + low
if (isEqual(strs, low, mid)) {
low = mid + 1
} else {
high = mid - 1
}
}
return strs[0].substring(0, low)
}
/**
* 判断字符数组中所有字符是否相同
* @param {string[]} strs
* @param {number} low
* @param {number} high
* @return {boolean}
*/
function isEqual(strs, low, high) {
let prefix = strs[0].substring(low, high + 1)
for (let i = 1; i < strs.length; i++) {
if (prefix !== strs[i].substring(low, high + 1)) {
return false
}
}
return true
}
