leetcode 14. Longest Common Prefix 最长公共前缀

红太狼 2022-06-09 06:55 85阅读 0赞

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

题意是给了一个字符串的数组，找到所有的最长公共前缀。  
这个题很简单，寻找最长公共前缀要比找最常供子串要简单多了，只需要顺序的比对即可，遇到不同的地方就表示公共前缀结束。

代码如下：

/*
     * 找最长公共前缀必要找最常供子串要简单许多了，只需要两两比较即可
     * 只要遇到不同的字符就表示公共前缀结束
     * */
    public class Solution 
    {
        public String longestCommonPrefix(String[] strs) 
        {
            if(strs==null || strs.length<=0)
                return "";
            if(strs.length==1)
                return strs[0];
    
            String tmp=getCommonPrefix(strs[0],strs[1]);
            for(int i=2;i<strs.length;i++)
            {
                tmp=getCommonPrefix(tmp,strs[i]);
                if(tmp==null || tmp.length()<=0)
                    break;
            }
            return tmp;
        }
    
        private String getCommonPrefix(String tmp, String string)
        {
            int len=Math.min(tmp.length(), string.length());
            int i=0;
            for(i=0;i<len;i++)
            {
                if(tmp.charAt(i)!=string.charAt(i))
                    break;
            }
            return tmp.substring(0,i);
        }
    }

C++答案如下，求解最长公共前缀很简单的，直接遍历求解即可。

代码如下：

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    
    class Solution 
    {
    public:
        string longestCommonPrefix(vector<string>& strs) 
        {
            if (strs.size() <= 0)
                return "";
    
            string res = strs[0];
            for (int i = 1; i < strs.size(); i++)
                res = getCommonPre(res, strs[i]);
            return res;
        }
    
        string getCommonPre(string a, string b)
        {
            string res = "";
            int i = 0, j = 0;
            while (i < a.length() && j < b.length())
            {
                if (a[i] == b[j])
                {
                    res += a[i];
                    i++;
                    j++;
                }
                else
                    break;
            }
            return res;
        }
    };