lintcode78. 最长公共前缀

刺骨的言语ヽ痛彻心扉 2023-07-03 10:35 4阅读 0赞

给k个字符串，求出他们的最长公共前缀(LCP)

样例
    样例 1:
    	输入:  "ABCD", "ABEF", "ACEF"
    	输出:  "A"
    	
    
    样例 2:
    	输入: "ABCDEFG", "ABCEFG" and "ABCEFA"
    	输出:  "ABC"

class Solution {
        
    public:
        /**
         * @param strs: A list of strings
         * @return: The longest common prefix
         */
        string longestCommonPrefix(vector<string> &strs) {
        
            // write your code here
            if(strs.size()==0) return"";
            else if(strs.size()==1) return strs[0];
            int count=0;
            int minlen=INT_MAX;
            for (int i = 0; i < strs.size(); i++) {
        
                /* code */
                minlen=minlen<strs[i].size()?minlen:strs[i].size();//找到最小长度
                if(i>0&&strs[i][0]!=strs[i-1][0]) return "";//如果是在第一个单词就出现错误，则返回空
            }
            bool judge=true;
            while(judge&&count<minlen)
            {
        
                char tmp=strs[0][count];
                for (int i = 0; i < strs.size()&&count<minlen; i++) {
        
                    /* code */
                    if(strs[i][count]!=tmp)
                    {
        
                        judge=false;
                    }
                }
                count++;
            }
            if(count-1==0) return strs[0];//只有一个单词，如A,A的情况，则须返回第一个
            else if (minlen == count&&judge) return string(strs[0], 0, count);//如果前面字符都相同，因为长度限制则返回最小长度的那个字符
            return string(strs[0],0,count-1);
        }
    };

class Solution {
        
    public:
        /**
         * @param strs: A list of strings
         * @return: The longest common prefix
         */
        string longestCommonPrefix(vector<string> &strs) {
        
            // write your code here
            if(strs.size()==0) return"";
            else if(strs.size()==1) return strs[0];
            int count=0;
            int minlen=INT_MAX;
            for (int i = 0; i < strs.size(); i++) {
        
                /* code */
                minlen=minlen<strs[i].size()?minlen:strs[i].size();//找到最小长度
            }
            bool judge=true;
            string result="";
            while(judge&&count<minlen)
            {
        
                char tmp=strs[0][count];
                for (int i = 0; i < strs.size()&&count<minlen; i++) {
        
                    /* code */
                    if(strs[i][count]!=tmp)
                    {
        
                        judge=false;
                    }
                }
                if(judge) result+=strs[0][count];
                count++;
            }
            return result;
        }
    };