Last Updated on 2021-01-07 by Clay
題目
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:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""題目給定一陣列，裡頭存放許多組字串，而我們要做的就是找到他們共同的前綴字串並回傳；若無共同的前綴，則回傳空字串 “”。
解題思路
這題我使用了比較暴力的方法直接做比對。
C++ 程式碼
class Solution { public: string longestCommonPrefix(vector<string>& strs) { // Preventation if (strs.empty()) return ""; if (strs.size() == 1) return strs[0]; // Init string ans = ""; int min_len = 200; for (string str: strs) { if (str.size() < min_len) { min_len = str.size(); } } // Comparison for (int i=0; i<min_len; i++) { for (int si=0; si<strs.size()-1; si++) { if (strs[si][i] != strs[si+1][i]) { return ans; } } ans += strs[0][i]; } return ans; } };
Python 程式碼
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: # Preventation if not strs: return '' if len(strs) == 1: return strs[0] # Init ans = "" min_len = 200 for s in strs: if len(s) < min_len: min_len = len(s) # Comparison for i in range(min_len): for si in range(len(strs)-1): if (strs[si][i] != strs[si+1][i]): return ans ans += strs[si][i] return ans