14.最长公共前缀

LeetCode LeetCode 字符串 字典树
发布时间 :
字数:3k 阅读 : 评论:
  1. 14.最长公共前缀
    1. 14.1 题目
    2. 14.2 题解
      1. 遍历每个字符串的每个字符，找到最长公共前缀
      2. 两两字符逐个比较 逐渐缩小并更新前缀长度
      3. 分治分割字符串数组两两比较后递归返回前缀
    3. 14.3 代码
    4. 14.4 运行结果

14.最长公共前缀

14.1 题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例：

  • 示例 1：

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

  • 示例 2：

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

提示：

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

14.2 题解

遍历每个字符串的每个字符，找到最长公共前缀

// 方法一：遍历每个字符串的每个字符，找到最长公共前缀
static string LongestCommonPrefix1(string[] strs)
{
    // 如果输入的字符串数组为空或长度为0，返回空字符串
    if (strs == null || strs.Length == 0)
    {
        return "";
    }

    // 获取字符串数组中最短字符串的长度
    int minStringLength = GetMinStringLength(strs);


    // 使用 StringBuilder 构建最终的最长公共前缀
    StringBuilder stringBuilder = new StringBuilder();

    // 遍历每个字符位置，直到最短字符串的长度
    for (int i = 0; i < minStringLength; i++)
    {
        // 如果在当前字符位置所有字符串的字符相同，则将该字符添加到结果中
        if (CompareStringsIndexCharIsEqual(strs, i))
        {
            stringBuilder.Append(strs[0][i]);
        }
        // 如果在当前字符位置有不相同的字符，停止遍历
        else
        {
            break;
        }
    }

    // 返回构建的最长公共前缀
    return stringBuilder.ToString();
}

// 获取字符串数组中的最小字符串长度
static int GetMinStringLength(string[] strs)
{
    // 如果数组为空或长度为0，抛出异常
    if (strs == null || strs.Length == 0)
    {
        return 0;
    }

    // 初始化最小长度为第一个字符串的长度
    int minLength = strs[0].Length;

    // 遍历数组，找出最短字符串的长度
    foreach (string str in strs)
    {
        int currentLength = str.Length;

        // 如果当前字符串长度小于最小长度，更新最小长度
        if (currentLength < minLength)
        {
            minLength = currentLength;
        }
    }

    // 返回最小长度
    return minLength;
}

// 比较所有字符串在指定位置的字符是否相同
static bool CompareStringsIndexCharIsEqual(string[] strs, int i)
{
    // 获取第一个字符串在指定位置的字符
    char charValue = strs[0][i];

    // 遍历其余字符串，检查字符是否相同
    for (int j = 1; j < strs.Length; j++)
    {
        // 如果当前字符位置超过当前字符串的长度，或字符不相同，返回 false
        if (i >= strs[j].Length || strs[j][i] != charValue)
        {
            return false;
        }
    }

    // 如果所有字符串在指定位置的字符都相同，返回 true
    return true;
}

两两字符逐个比较 逐渐缩小并更新前缀长度

// 方法二：两两字符逐个比较 逐渐缩小并更新前缀长度
static string LongestCommonPrefix2(string[] strs)
{
    // 如果数组为空，可以根据实际需求返回一个默认值或抛出异常
    if (strs == null || strs.Length == 0)
    {
        return "";
    }

    // 将第一个字符串设置为初始比较字符串
    string compareStr = strs[0];

    // 将初始比较字符串设置为结果字符串
    string resultStr = compareStr;

    // 遍历字符串数组，从第二个字符串开始比较
    for (int arrayIndex = 1; arrayIndex < strs.Length; arrayIndex++)
    {
        // 每次两两比较前将结果字符串重置为空字符串
        resultStr = "";

        // 遍历当前字符串和比较字符串的每个字符
        for (int stringIndex = 0;
                stringIndex < strs[arrayIndex].Length && stringIndex < compareStr.Length;
                stringIndex++)
        {
            // 如果当前字符和比较字符串的对应字符相同，将该字符添加到结果字符串
            if (strs[arrayIndex][stringIndex] == compareStr[stringIndex])
            {
                resultStr += compareStr[stringIndex];
            }
            else
            {
                // 如果遇到不同的字符，结束当前字符位置的比较
                break;
            }
        }

        // 将比较字符串更新为当前比较的结果字符串
        compareStr = resultStr;

        // 如果比较字符串为空，表示没有公共前缀，结束循环
        if (compareStr == "")
        {
            break;
        }
    }

    // 返回最终的结果字符串，即最长的公共前缀
    return resultStr;
}

分治分割字符串数组两两比较后递归返回前缀

// 方法三：分治分割字符串数组两两比较后递归返回前缀
static string LongestCommonPrefix3(string[] strs)
{
    // 如果数组为空，可以根据实际需求返回一个默认值或抛出异常
    if (strs == null || strs.Length == 0)
    {
        return "";
    }

    // 调用递归方法，传入字符串数组、起始索引和结束索引
    return SplitStrs(strs, 0, strs.Length - 1);
}

// 分割字符串数组递归方法，将字符串数组分为左右两部分，然后比较左右两部分的最长公共前缀
static string SplitStrs(string[] strs, int startIndex, int endIndex)
{
    // 如果起始索引和结束索引相等，说明只有一个字符串，直接返回该字符串
    if (startIndex == endIndex)
    {
        return strs[startIndex];
    }
    else
    {
        // 计算中间索引，用于将数组分为左右两部分
        int middleIndex = (endIndex + startIndex) / 2;

        // 递归调用，分别处理左右两部分的字符串数组
        string leftStr = SplitStrs(strs, startIndex, middleIndex);
        string rightStr = SplitStrs(strs, middleIndex + 1, endIndex);

        // 调用比较方法，比较左右两部分的最长公共前缀
        return CompareStr(leftStr, rightStr);
    }
}

// 比较两个字符串的最长公共前缀并返回
static string CompareStr(string leftStr, string rightStr)
{
    // 初始化StringBuilder用于构建公共前缀字符串
    StringBuilder stringBuilder = new StringBuilder();

    // 遍历两个字符串的每个字符，比较它们是否相等
    // 遍历的次数为两个字符串中较短的那个的长度
    for (int i = 0; i < Math.Min(leftStr.Length, rightStr.Length); i++)
    {
        // 如果当前字符相等，将该字符添加到StringBuilder中
        if (leftStr[i] == rightStr[i])
        {
            stringBuilder.Append(leftStr[i]);
        }
        // 如果字符不相等，说明公共前缀结束，退出循环
        else
        {
            break;
        }
    }

    // 将StringBuilder中的字符转换为字符串并返回
    return stringBuilder.ToString();
}

14.3 代码

using System;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 编写一个函数来查找字符串数组中的最长公共前缀。
        // 如果不存在公共前缀，返回空字符串 ""。

        // 示例 1：
        // 输入：strs = ["flower","flow","flight"]
        // 输出："fl"

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

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

        #endregion

        #region 测试

        // 示例 1
        string[] strs1 = { "flower", "flow", "flight" };
        string result11 = LongestCommonPrefix1(strs1);
        Console.WriteLine($"示例1 方法1 输出：{result11}");
        string result12 = LongestCommonPrefix2(strs1);
        Console.WriteLine($"示例1 方法2 输出：{result12}");
        string result13 = LongestCommonPrefix3(strs1);
        Console.WriteLine($"示例1 方法3 输出：{result13}");

        // 示例 2
        string[] strs2 = { "dog", "racecar", "car" };
        string result21 = LongestCommonPrefix1(strs2);
        Console.WriteLine($"示例2 方法1 输出：{result21}");
        string result22 = LongestCommonPrefix2(strs2);
        Console.WriteLine($"示例2 方法2 输出：{result22}");
        string result23 = LongestCommonPrefix3(strs2);
        Console.WriteLine($"示例2 方法3 输出：{result23}");

        #endregion
    }

    #region 答案

    // 方法一：遍历每个字符串的每个字符，找到最长公共前缀
    static string LongestCommonPrefix1(string[] strs)
    {
        // 如果输入的字符串数组为空或长度为0，返回空字符串
        if (strs == null || strs.Length == 0)
        {
            return "";
        }

        // 获取字符串数组中最短字符串的长度
        int minStringLength = GetMinStringLength(strs);


        // 使用 StringBuilder 构建最终的最长公共前缀
        StringBuilder stringBuilder = new StringBuilder();

        // 遍历每个字符位置，直到最短字符串的长度
        for (int i = 0; i < minStringLength; i++)
        {
            // 如果在当前字符位置所有字符串的字符相同，则将该字符添加到结果中
            if (CompareStringsIndexCharIsEqual(strs, i))
            {
                stringBuilder.Append(strs[0][i]);
            }
            // 如果在当前字符位置有不相同的字符，停止遍历
            else
            {
                break;
            }
        }

        // 返回构建的最长公共前缀
        return stringBuilder.ToString();
    }

    // 获取字符串数组中的最小字符串长度
    static int GetMinStringLength(string[] strs)
    {
        // 如果数组为空或长度为0，抛出异常
        if (strs == null || strs.Length == 0)
        {
            return 0;
        }

        // 初始化最小长度为第一个字符串的长度
        int minLength = strs[0].Length;

        // 遍历数组，找出最短字符串的长度
        foreach (string str in strs)
        {
            int currentLength = str.Length;

            // 如果当前字符串长度小于最小长度，更新最小长度
            if (currentLength < minLength)
            {
                minLength = currentLength;
            }
        }

        // 返回最小长度
        return minLength;
    }

    // 比较所有字符串在指定位置的字符是否相同
    static bool CompareStringsIndexCharIsEqual(string[] strs, int i)
    {
        // 获取第一个字符串在指定位置的字符
        char charValue = strs[0][i];

        // 遍历其余字符串，检查字符是否相同
        for (int j = 1; j < strs.Length; j++)
        {
            // 如果当前字符位置超过当前字符串的长度，或字符不相同，返回 false
            if (i >= strs[j].Length || strs[j][i] != charValue)
            {
                return false;
            }
        }

        // 如果所有字符串在指定位置的字符都相同，返回 true
        return true;
    }


    // 方法二：两两字符逐个比较 逐渐缩小并更新前缀长度
    static string LongestCommonPrefix2(string[] strs)
    {
        // 如果数组为空，可以根据实际需求返回一个默认值或抛出异常
        if (strs == null || strs.Length == 0)
        {
            return "";
        }

        // 将第一个字符串设置为初始比较字符串
        string compareStr = strs[0];

        // 将初始比较字符串设置为结果字符串
        string resultStr = compareStr;

        // 遍历字符串数组，从第二个字符串开始比较
        for (int arrayIndex = 1; arrayIndex < strs.Length; arrayIndex++)
        {
            // 每次两两比较前将结果字符串重置为空字符串
            resultStr = "";

            // 遍历当前字符串和比较字符串的每个字符
            for (int stringIndex = 0;
                 stringIndex < strs[arrayIndex].Length && stringIndex < compareStr.Length;
                 stringIndex++)
            {
                // 如果当前字符和比较字符串的对应字符相同，将该字符添加到结果字符串
                if (strs[arrayIndex][stringIndex] == compareStr[stringIndex])
                {
                    resultStr += compareStr[stringIndex];
                }
                else
                {
                    // 如果遇到不同的字符，结束当前字符位置的比较
                    break;
                }
            }

            // 将比较字符串更新为当前比较的结果字符串
            compareStr = resultStr;

            // 如果比较字符串为空，表示没有公共前缀，结束循环
            if (compareStr == "")
            {
                break;
            }
        }

        // 返回最终的结果字符串，即最长的公共前缀
        return resultStr;
    }


    // 方法三：分治分割字符串数组两两比较后递归返回前缀
    static string LongestCommonPrefix3(string[] strs)
    {
        // 如果数组为空，可以根据实际需求返回一个默认值或抛出异常
        if (strs == null || strs.Length == 0)
        {
            return "";
        }

        // 调用递归方法，传入字符串数组、起始索引和结束索引
        return SplitStrs(strs, 0, strs.Length - 1);
    }

    // 分割字符串数组递归方法，将字符串数组分为左右两部分，然后比较左右两部分的最长公共前缀
    static string SplitStrs(string[] strs, int startIndex, int endIndex)
    {
        // 如果起始索引和结束索引相等，说明只有一个字符串，直接返回该字符串
        if (startIndex == endIndex)
        {
            return strs[startIndex];
        }
        else
        {
            // 计算中间索引，用于将数组分为左右两部分
            int middleIndex = (endIndex + startIndex) / 2;

            // 递归调用，分别处理左右两部分的字符串数组
            string leftStr = SplitStrs(strs, startIndex, middleIndex);
            string rightStr = SplitStrs(strs, middleIndex + 1, endIndex);

            // 调用比较方法，比较左右两部分的最长公共前缀
            return CompareStr(leftStr, rightStr);
        }
    }

    // 比较两个字符串的最长公共前缀并返回
    static string CompareStr(string leftStr, string rightStr)
    {
        // 初始化StringBuilder用于构建公共前缀字符串
        StringBuilder stringBuilder = new StringBuilder();

        // 遍历两个字符串的每个字符，比较它们是否相等
        // 遍历的次数为两个字符串中较短的那个的长度
        for (int i = 0; i < Math.Min(leftStr.Length, rightStr.Length); i++)
        {
            // 如果当前字符相等，将该字符添加到StringBuilder中
            if (leftStr[i] == rightStr[i])
            {
                stringBuilder.Append(leftStr[i]);
            }
            // 如果字符不相等，说明公共前缀结束，退出循环
            else
            {
                break;
            }
        }

        // 将StringBuilder中的字符转换为字符串并返回
        return stringBuilder.ToString();
    }


    #endregion
}

14.4 运行结果

示例1 方法1 输出：fl
示例1 方法2 输出：fl
示例1 方法3 输出：fl
示例2 方法1 输出：
示例2 方法2 输出：
示例2 方法3 输出：
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏