最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

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

示例 1：

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

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

• class Solution {
  public:
      string longestCommonPrefix(vector<string>& strs) {
           if(strs.size()<1)return "";
             sort(strs.begin(),strs.end());
             
            string s=strs[0];
            if(strs.size()<2)return s;
             int start=0; 
             for(int i=1;i<strs.size();i++)
              {
                  int ma=0;
                   string s1=strs[i];              
                   for(int j=0;j<s.length();j++)
                    {
          
                      if(s[j]==s1[j]) ma++;
                      else break;   
                    }
                    if(ma==0)return "";
                    s= s.substr(start,ma);
              }
  
              
           return s;
      } 
  };

  最大公共子缀

• class Solution {
  public:
      string longestCommonPrefix(vector<string>& strs) {
           if(strs.size()<1)return "";
             sort(strs.begin(),strs.end());
             
            string s=strs[0];
            if(strs.size()<2)return s;
            int ma=0; int start=0; 
             for(int i=1;i<strs.size();i++)
              {
                  
                   string s1=strs[i];
                   vector<vector<int> > dp(200,vector<int>(200,0));
                  
                   for(int j=1;j<=s.length();j++)
                    {
          
                                  if(s[k-1]==s1[j-1])dp[j][k]=dp[j-1][k-1]+1;
                                  if(ma<dp[j][k])
                                  {
                                      ma=dp[j][k];
                                      start=j-ma;
                                  }
                           }
                            
                    }
                    s= s.substr(start,ma);
              }
  
              
           return s;
      } 
  };