14. 最長公共前綴

14. 最長公共前綴

代碼倉庫地址： https://github.com/slience-me/Leetcode

個人博客 ：https://slienceme.xyz

• 編寫一個函數來查找字符串數組中的最長公共前綴。

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

示例 1：

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

示例 2：

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

提示：

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

方案1：暴力解 歷史最差代碼沒有之一

第一種純暴力解，很多不合理的地方，考場上只是為了拿基礎分，就是結果導向性解題方式

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if (strs[0] == ""){return "";}int maxsize = -1;for (const auto &item: strs){maxsize = max(maxsize, static_cast<int>(item.size()));}string res;for (int i = 0; i < maxsize; ++i) {char temp = strs[0][i];string tmp ;for (int j = 0; j < strs.size(); ++j) {if (temp == strs[j][i]){cout<<"temp: "<<temp<<"   strs[j][i]: "<<strs[j][i]<<"  i: "<<i<<" j: "<<j<<endl;tmp = strs[j][i];} else {tmp = "";goto outerLoop; // 跳到外層循環的標簽位置}}res.append(tmp);}outerLoop:return res;}
};

執行用時分布 48ms 擊敗6.69%使用 C++ 的用戶

消耗內存分布9.37MB 擊敗15.46%使用 C++ 的用戶

方案2

初次優化，這種方案比上一種更加合理，去除掉了很多冗余的代碼
i >= s.length()關鍵條件 s[i] != tmp

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string res;for (int i = 0; i < 200; ++i) {if (i > strs[0].length())return res; //處理空情況char tmp = strs[0][i];for (const auto &s: strs) {if (i >= s.length())return res;// 超出了，則說明當前字符串長度不夠 flower flow  i=5 >= 4if (s[i] != tmp)return res;}res += tmp;}return res;}
};

執行用時分布 0ms 擊敗100%使用 C++ 的用戶

消耗內存分布 9.04MB 擊敗63.16%使用 C++ 的用戶

方案3

最后的優化，沒有太大的提升

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ans = "";// 用第一個單詞的字符一次遍歷全部字符串for (int i = 0; i < strs[0].size(); ++i) {bool flag = true;for (int j = 1; j < strs.size(); ++j) {if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {flag = false; // 合二為一break; // 退出里循環}}if (flag) {ans += strs[0][i];} else {break; // 退出外循環}}return ans;}
};

執行用時分布 4ms 擊敗%使用 C++ 的用戶

消耗內存分布 9.12MB 擊敗46.03%使用 C++ 的用戶