014 Longest Common Prefix[E]

1 題目描述

Write a function to find the longest common prefix string amongst an array of strings.

難度：Easy

2 題目樣例

無。

3 題目分析

給出一個字元串數組，要求返回其中包含的所有字元串的最長公共前綴。

如果沒有公共的前綴的話，返回的自然是""了。

4 思路分析

這道題目雖然簡單，但解法卻是多種多樣的，不過思想上都不難，在此收錄最常見的方法供參考，希望讀者在看了這些解法之後能開拓思路。如果有更好的方法，可以在評論區分享給大家。

一個比較嚴肅（可能只是因為我太愚鈍了）的問題是，多數的方法似乎在時間複雜度上都沒有顯著的提升。

我的方法是：套用兩重for循環，逐位判斷即可。如果我們發現當前某個字元和下一行對應位置的字元不相等，說明不會再有更長的共同前綴了，我們直接通過用substr的方法直接取出共同前綴的子字元串。

如果遍歷結束前沒有返回結果的話，說明第一個單詞就是公共前綴，返回為結果即可。

順帶一提，要記得特判strs為空的情況，否則會產生一個REG的錯誤。

代碼實現如下：

class Solution { public: string longestCommonPrefix(vector<string>& strs) { if(strs.empty()) return ""; for(int i=0;i<strs[0].size();i++) for(int j=1;j<strs.size();j++) { if(i>=strs[j].size() || strs[j][i]!=strs[0][i]) return strs[0].substr(0,i); } return strs[0]; }};

5 後記

我嘗試著在提交之後讀了讀3ms的示例代碼，感覺思想上和我的代碼並沒有什麼區別啊...

推薦閱讀：