Leetcode: Longest Common Prefix

柔情只为你懂 2022-08-07 06:57 95阅读 0赞

题目：  
Write a function to find the longest common prefix string amongst an array of strings.  
即求给定的一组字符串的公共前缀。

思路分析：  
一个一个寻找前缀，先比较第一个和第二个，找到公共前缀，然后公共前缀和第三个比较，寻找公共前缀，以此类推。

C++参考代码：

class Solution
    {
    public:
        string longestCommonPrefix(vector<string> &strs)
        {
            if (strs.empty())
            {
                return "";
            }
            string common = strs[0];
            vector<string>::size_type size = strs.size();
            int length;//保存要比较的两个字符串的最小长度，只在最小长度范围内进行比较
            int count;//记录相等的字符个数
            for (int i = 1; i < size; i++)
            {
                length = min(common.length(), strs[i].length());
                count = 0;
                for (int j = 0; j < length; j++)
                {
                    //如果两个字符相等count++
                    if (strs[i][j] == common[j])
                    {
                        count++;
                    }
                    //如果两个字符不相等直接退出内层循环
                    else
                    {
                        break;
                    }
                }
                //将common和strs[i]的共同前缀保存在common中，进行下一个字符的比较
                common = common.substr(0, count);
            }
            return common;
        }
    };

C\#参考代码：

public class Solution { 
        public string LongestCommonPrefix(string[] strs)
        {
            if (strs == null || strs.Length == 0)
            {
                return string.Empty;
            }
            string common = strs[0];
            int length = 0;
            int count = 0;
            for (int i = 1; i < strs.Length; i++)
            {
                length = Math.Min(common.Length, strs[i].Length);
                count = 0;
                for (int j = 0; j < length; j++)
                {
                    if (strs[i][j] == common[j])
                    {
                        count++;
                    }
                    else
                    {
                        break;
                    }
                }
                common = common.Substring(0, count);
            }
            return common;
        }
    }

Python参考代码：

class Solution:
        # @return a string
        def longestCommonPrefix(self, strs):
            size = len(strs)
            if not strs or size == 0:
                return ""
            common = strs[0]
            length = 0
            count = 0
            for i in range(1, size):
                length = min(len(common), len(strs[i]))
                count = 0
                for j in range(length):
                    if strs[i][j] == common[j]:
                        count += 1
                    else:
                        break
                common = common[0: count]
            return common