溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

leetcode中如何解決最長(zhǎng)公共前綴問(wèn)題

發(fā)布時(shí)間：2022-01-17 11:49:29 來(lái)源：億速云 閱讀：204 作者：小新 欄目：大數(shù)據(jù)

這篇文章主要介紹leetcode中如何解決最長(zhǎng)公共前綴問(wèn)題，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

 

題目鏈接

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

 

題目描述

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

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

示例 1:

輸入: ["flower","flow","flight"]輸出: "fl"
 

示例 2:

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

說(shuō)明:

所有輸入只包含小寫字母 a-z 。

 

解題方案

 

思路

  • 標(biāo)簽：字符串

  • 當(dāng)字符串?dāng)?shù)組長(zhǎng)度為0時(shí)則公共前綴為空，直接返回

  • 令最長(zhǎng)公共前綴ans的值為第一個(gè)字符串，進(jìn)行初始化

  • 遍歷后面的字符串，依次將其與ans進(jìn)行比較，兩兩找出公共前綴，最終結(jié)果即為最長(zhǎng)公共前綴

  • 如果查找過(guò)程中出現(xiàn)了ans為空的情況，則公共前綴不存在直接返回

  • 時(shí)間復(fù)雜度：O(s)，s為所有字符串的長(zhǎng)度之和

 

代碼

  • Java版本

class Solution {    public String longestCommonPrefix(String[] strs) {        if(strs.length == 0)             return "";        String ans = strs[0];        for(int i =1;i<strs.length;i++) {            int j=0;            for(;j<ans.length() && j < strs[i].length();j++) {                if(ans.charAt(j) != strs[i].charAt(j))                    break;            }            ans = ans.substring(0, j);            if(ans.equals(""))                return ans;        }        return ans;    }}
 

  • JavaScript版本

/** * @param {string[]} strs * @return {string} */var longestCommonPrefix = function(strs) {    if(strs.length == 0)         return "";    let ans = strs[0];    for(let i =1;i<strs.length;i++) {        let j=0;        for(;j<ans.length && j < strs[i].length;j++) {            if(ans[j] != strs[i][j])                break;        }        ans = ans.substr(0, j);        if(ans === "")            return ans;    }    return ans;};
 
 

畫解

leetcode中如何解決最長(zhǎng)公共前綴問(wèn)題leetcode中如何解決最長(zhǎng)公共前綴問(wèn)題leetcode中如何解決最長(zhǎng)公共前綴問(wèn)題

以上是“l(fā)eetcode中如何解決最長(zhǎng)公共前綴問(wèn)題”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手