【剑斩OFFER】算法的暴力美学——最长公共前缀

一、题目描述

二、算法原理

思路：先找前两个字符串的公共前缀，再拿着这个公共前缀的，去跟剩余的字符串比较，然后不断的更新这个公共前缀：

三、代码实现

第一种解法：

class Solution { public: string longestCommonPrefix(vector<string>& strs) { if(strs.size() < 2) return strs[0]; string same; string s1 = strs[0],s2 = strs[1]; for(int i = 0; i < min(s1.size(),s2.size()); i++)//找到第一个字符和第二个字符串的公共字符串 { if(s1[i] == s2[i]) same += s1[i]; else break; } for(int i = 2; i < strs.size(); i++)//拿着公共字符串去和其他字符串进行比较 { string& s = strs[i]; string tmp; for(int j = 0; j < min(same.size(),s.size()); j++) { if(s[j] == same[j]) tmp += s[j]; else break; } same = tmp;//更新公共字符串 if(same.empty()) return ""; } return same; } };

第二种解法：

class Solution { public: string longestCommonPrefix(vector<string>& strs) { string same;//公共前缀 for(int i = 0; i < strs[0].size(); i++) { char ch = strs[0][i]; for(int j = 0; j < strs.size();j++) { char ch1 = strs[j][i]; if(ch1 != ch) return same;//找到公共前缀的极限，直接返回 same ，因为后面的都不是公共前缀 } same += ch; } return same; } };