【C#知识点】公共前缀问题详解——substring、any、all

今天在刷leetcode时看到一道标签为“简单”的题目，说是简单，对我这种C#新人、自学编程和算法的还是很有困难的。不过从这道题中学了些知识点，于是想记录一下。

原题 
1
2
3
4
5
6
7
8
9
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

整体思路

看到这道题，我的思路是：首先我们进行两次遍历，第一次遍历strs的所有元素，第二次遍历我们把字符串当成数组、拿出字符来分别比较。至于字符的添加，我们用StringBuilder的append方法去加。 于是在我苦思冥想下、诞生了第一种笨蛋方法： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution
{
    public String LongestCommonPrefix(String[] strs)
    {
        //判断特殊情况，字符为空
        if (strs == null || strs.Length == 0)
        {
            return "";
        }

        int length = strs.Length;
        //我用count存储第一个字符串的长度
        int count = strs[0].Length;
        //我对字符串长度进行更新，找出最短的。
        for (int i = 1; i < length; i++)
        {
            count = Math.Min(count, strs[i].Length); // 更新count为当前最短字符串的长度
        }
        //StringBuilder实例化
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < count; j++)
        {
            char currentChar = strs[0][j];
            for (int i = 1; i < length; i++)
            {
                if (j >= strs[i].Length || strs[i][j] != currentChar)
                {
                    return sb.ToString(); // 如果当前字符不匹配或超出了某个字符串的长度，返回当前构建的公共前缀
                }
            }
            sb.Append(currentChar); // 将匹配的字符添加到公共前缀中
        }
        return sb.ToString();
    }
}

以上代码又臭又长，时间和内存上成功打败了30%和50%的同学，不太合适。

SubString来解题

于是我了解到一个方法，名叫SubString： 我们定义一个数组：string str = "Hello,World"; SubString有两个重载： string str1 = str.SubString(0,5)表示从索引0的位置开始、长度为五的字符串,打印出来就是Hello; string str2 = str.SubString(6)表示从索引为6的位置打印，打印出它和它之后的字符，就是World; 于是乎，诞生了一个新思路：我们拿strs[0]开始，找到最后一个索引j,那个位置正好strs[0][j]等于strs[i][j],之后用SubString方法就简单了： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution
{
    public String LongestCommonPrefix(String[] strs)
    {
        if (strs.Length == 0)
        {
            return "";
        }

        string prefix = strs[0];
        for (int i = 1; i < strs.Length; i++)
        {
            int j = 0;
            //while循环直接把条件限制死
            while (j < prefix.Length && j < strs[i].Length && prefix[j] == strs[i][j])
            {
                j++;
            }
            if (j == 0)
            {
                return "";
            }
            prefix = prefix.Substring(0, j);
        }
        return prefix;
    }
}

于是以上代码在时间和内存上分别击败了74%和83%的同学。

大佬解法

于是乎，我有通过大佬解法了解到很多知识点： Any：本质上是个委托，装载匿名函数；是个布尔运算，如果至少有一个元素满足条件，它返回 true，否则返回 false。（与之相对的有All） =>:lambda表达式，与匿名函数使用 <=:布尔运算符，如果左边小于等于右边返回true，否则是false .. :C#新引入的东西，strs[0][..i]就表示新创建个string，它由strs[0][0]到strs[0][i - 1]间所有字符组成。（不包括 i） s: 我们传入的字符串中的每个元素 第一种情况：我们传入的元素的长度小于我们的索引，它已经检查到末尾了，的所有字符都符合我们的前缀，于是有了s.Length <= i 第二种情况：检查到i的位置，发现不相等了。于是s[i] != strs[0][i] 这两种情况、只要出现任意一种都行。 最后我们返回从strs[0]一直到strs[0][i](不包括strs[0][i])之间的所有字符组成的字符串，就有了return strs[0][..i]; 
1
2
3
4
5
6
7
8
9
10
public class Solution
{
    public string LongestCommonPrefix(string[] strs)
    {
        for (var i = 0; ; i++)
        //Any能遍历所有元素，传入的s就是我们数组的元素的代表。
            if (strs.Any(s => s.Length <= i || s[i] != strs[0][i]))
                return strs[0][..i]；
    }
}

我们代码进行了：先判断i有没有超过数字长度、strs的字符是否相等——没问题，i++;
等到以上任意一种情况不符合了————突然不相等了、或者最短的字符串所有字符都符合——Any判定为true，就终止循环了
如此很奇妙地解决问题，这下代码就很精简了。