C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)
[LeetCode] 14. Longest Common Prefix 最長(zhǎng)共同前綴
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
.
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
這道題讓我們求一系列字符串的共同前綴,沒有什么特別的技巧,無腦查找即可,定義兩個(gè)變量i和j,其中i是遍歷搜索字符串中的字符,j是遍歷字符串集中的每個(gè)字符串。這里將單詞上下排好,則相當(dāng)于一個(gè)各行長(zhǎng)度有可能不相等的二維數(shù)組,遍歷順序和一般的橫向逐行遍歷不同,而是采用縱向逐列遍歷,在遍歷的過程中,如果某一行沒有了,說明其為最短的單詞,因?yàn)楣餐熬Y的長(zhǎng)度不能長(zhǎng)于最短單詞,所以此時(shí)返回已經(jīng)找出的共同前綴。每次取出第一個(gè)字符串的某一個(gè)位置的單詞,然后遍歷其他所有字符串的對(duì)應(yīng)位置看是否相等,如果有不滿足的直接返回 res,如果都相同,則將當(dāng)前字符存入結(jié)果,繼續(xù)檢查下一個(gè)位置的字符,參見代碼如下:
C++ 解法一:
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; string res = ""; for (int j = 0; j < strs[0].size(); ++j) { char c = strs[0][j]; for (int i = 1; i < strs.size(); ++i) { if (j >= strs[i].size() || strs[i][j] != c) { return res; } } res.push_back(c); } return res; } };
Java 解法一:
public class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; String res = new String(); for (int j = 0; j < strs[0].length(); ++j) { char c = strs[0].charAt(j); for (int i = 1; i < strs.length; ++i) { if (j >= strs[i].length() || strs[i].charAt(j) != c) { return res; } } res += Character.toString(c); } return res; } }
我們可以對(duì)上面的方法進(jìn)行適當(dāng)精簡(jiǎn),如果發(fā)現(xiàn)當(dāng)前某個(gè)字符和第一個(gè)字符串對(duì)應(yīng)位置的字符不相等,說明不會(huì)再有更長(zhǎng)的共同前綴了,直接通過用 substr 的方法直接取出共同前綴的子字符串。如果遍歷結(jié)束前沒有返回結(jié)果的話,說明第一個(gè)單詞就是公共前綴,返回為結(jié)果即可。代碼如下:
C++ 解法二:
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; for (int j = 0; j < strs[0].size(); ++j) { for (int i = 0; i < strs.size(); ++i) { if (j >= strs[i].size() || strs[i][j] != strs[0][j]) { return strs[i].substr(0, j); } } } return strs[0]; } };
Java 解法二:
class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; for (int j = 0; j < strs[0].length(); ++j) { for (int i = 0; i < strs.length; ++i) { if (j >= strs[i].length() || strs[i].charAt(j) != strs[0].charAt(j)) { return strs[i].substring(0, j); } } } return strs[0]; } }
我們?cè)賮砜匆环N解法,這種方法給輸入字符串?dāng)?shù)組排了個(gè)序,想想這樣做有什么好處?既然是按字母順序排序的話,那么有共同字母多的兩個(gè)字符串會(huì)被排到一起,而跟大家相同的字母越少的字符串會(huì)被擠到首尾兩端,那么如果有共同前綴的話,一定會(huì)出現(xiàn)在首尾兩端的字符串中,所以只需要找首尾字母串的共同前綴即可。比如例子1排序后為 ["flight", "flow", "flower"],例子2排序后為 ["cat", "dog", "racecar"],雖然例子2沒有共同前綴,但也可以認(rèn)為共同前綴是空串,且出現(xiàn)在首尾兩端的字符串中。由于是按字母順序排的,而不是按長(zhǎng)度,所以首尾字母的長(zhǎng)度關(guān)系不知道,為了防止溢出錯(cuò)誤,只遍歷而這種較短的那個(gè)的長(zhǎng)度,找出共同前綴返回即可,參見代碼如下:
C++ 解法三:
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; sort(strs.begin(), strs.end()); int i = 0, len = min(strs[0].size(), strs.back().size()); while (i < len && strs[0][i] == strs.back()[i]) ++i; return strs[0].substr(0, i); } };
Java 解法三:
class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; Arrays.sort(strs); int i = 0, len = Math.min(strs[0].length(), strs[strs.length - 1].length()); while (i < len && strs[0].charAt(i) == strs[strs.length - 1].charAt(i)) i++; return strs[0].substring(0, i); } }
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最長(zhǎng)共同前綴內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(88.混合插入有序數(shù)組)
- C++實(shí)現(xiàn)LeetCode(21.混合插入有序鏈表)
- C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))
- C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))
- C++實(shí)現(xiàn)LeetCode(18.四數(shù)之和)
- C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù))
- C++實(shí)現(xiàn)LeetCode(24.成對(duì)交換節(jié)點(diǎn))
相關(guān)文章
C/C++常用函數(shù)易錯(cuò)點(diǎn)分析
這篇文章主要介紹了C/C++常用函數(shù)易錯(cuò)點(diǎn)分析,包含了memset、sizeof、getchar三個(gè)常用函數(shù)的分析,需要的朋友可以參考下2014-08-08C++實(shí)現(xiàn)LeetCode(26.有序數(shù)組中去除重復(fù)項(xiàng))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(26.有序數(shù)組中去除重復(fù)項(xiàng)),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C++超詳細(xì)講解構(gòu)造函數(shù)與析構(gòu)函數(shù)的用法及實(shí)現(xiàn)
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值,構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無須手動(dòng)調(diào)用;析構(gòu)函數(shù)主要作用在于對(duì)象銷毀前系統(tǒng)自動(dòng)調(diào)用,執(zhí)行一?些清理工作2022-05-05C++共享智能指針shared_ptr的實(shí)現(xiàn)
在C++中沒有垃圾回收機(jī)制,必須自己釋放分配的內(nèi)存,否則就會(huì)造成內(nèi)存泄露,解決這個(gè)問題最有效的方法是使用智能指針,本文主要介紹了C++共享智能指針shared_ptr的實(shí)現(xiàn),感興趣的可以了解一下2023-12-12C++ 中動(dòng)態(tài)鏈接庫--導(dǎo)入和導(dǎo)出的實(shí)例詳解
這篇文章主要介紹了C++ 中動(dòng)態(tài)鏈接庫--導(dǎo)入和導(dǎo)出的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家,需要的朋友可以參考下2017-09-09從零學(xué)習(xí)cmake構(gòu)建系統(tǒng)
這篇文章主要為大家介紹了從零學(xué)習(xí)cmake構(gòu)建系統(tǒng)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02vs2019中使用MFC構(gòu)建簡(jiǎn)單windows窗口程序
今天發(fā)現(xiàn)網(wǎng)上好多MFC代碼都不能用,給大家分享一個(gè)簡(jiǎn)單的MFC窗口語言,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06vs2022重新編譯opencv-python?cuda加速時(shí)報(bào)錯(cuò)的問題解決
本文主要介紹了vs2022重新編譯opencv-python?cuda加速時(shí)報(bào)錯(cuò),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04C語言實(shí)現(xiàn)通訊錄的八種功能(添加、刪除、查找、修改、顯示、排序、退出、清空)
本文主要介紹了C語言實(shí)現(xiàn)通訊錄的八種功能,主要包括添加、刪除、查找、修改、顯示、排序、退出、清空,感興趣的可以了解一下2023-09-09