leetcode - 最長公共前綴

題意

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

示例

示例 1：

輸入：strs =?["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs =?["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示

• 0 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 僅由小寫英文字母組成

出處

鏈接：https://leetcode-cn.com/problems/longest-common-prefix

思路

這里我們需要拿字符串?dāng)?shù)組 strs 中的第一個字符串 str 進(jìn)行遍歷，然后如果說截取到的字符串 cur 滿足題意就把它賦值給 res，不滿足就退出循環(huán)。這里有一點就是你要單獨判斷數(shù)組為 0 的情況, 然后如果你是用 substr 函數(shù)截取的話，長度可以取等號的。當(dāng)然你也可以不借助 JS 的一些 API，手動遍歷，然后字符串相加求解。

代碼

巧用 JSAPI

/**
?*?@param?{string[]}?strs
?*?@return?{string}
?*/
const?longestCommonPrefix?=?function?(strs)?{
??if?(strs.length?===?0)?{
????return?'';
??}
??let?cur?=?'';
??let?res?=?'';
??for?(let?i?=?0;?i?<=?strs[0].length;?i++)?{
????cur?=?strs[0].substr(0,?i);
????if?(strs.every((str)?=>?str.startsWith(cur)))?{
??????res?=?cur;
????}?else?{
??????break;
????}
??}
??return?res;
};

export?default?longestCommonPrefix;

傳統(tǒng)的解法

/**
?*?@param?{string[]}?strs
?*?@return?{string}
?*/
const?longestCommonPrefix?=?function?(strs)?{
??let?res?=?'';
??if?(strs.length?!==?0)?{
????for?(let?i?=?0;?i?0].length;?i++)?{
??????if?(strs.every((str)?=>?str[i]?===?strs[0][i]))?{
????????res?+=?strs[0][i];
??????}?else?{
????????break;
??????}
????}
??}
??return?res;
};

export?default?longestCommonPrefix;

測試

import?longestCommonPrefix?from?'../../code/leetcode/14';

describe('test?function?longestCommonPrefix:',?()?=>?{
??test('test?case?strs?=?[]',?()?=>?{
????const?res?=?longestCommonPrefix([]);
????expect(res).toBe('');
??});

??test('test?case?strs?=?["flower","flow","flight"]',?()?=>?{
????const?res?=?longestCommonPrefix(['flower',?'flow',?'flight']);
????expect(res).toBe('fl');
??});

??test('test?case?strs?=?["dog","racecar","car"]',?()?=>?{
????const?res?=?longestCommonPrefix(['dog',?'racecar',?'car']);
????expect(res).toBe('');
??});

??test('test?case?strs?=?["flower","flower","flower","flower"]',?()?=>?{
????const?res?=?longestCommonPrefix(['flower',?'flower',?'flower',?'flower']);
????expect(res).toBe('flower');
??});

??test('test?case?strs?=?["a"]',?()?=>?{
????const?res?=?longestCommonPrefix(['a']);
????expect(res).toBe('a');
??});
});

說明

本文首發(fā)于 GitHub 倉庫https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉(zhuǎn)載請注明出處，謝謝！