算法编程题：字符串（8 题）

解题思路： 枚举 Rune，筛选字母数字并做不区分大小写的两端比较。

不变量： 每轮之前，左右边界之外的 Rune 已经成对匹配。

public static class AlgCode017Solution
{
    public static bool Solve(string text)
    {
        Rune[] values = text
            .EnumerateRunes()
            .Where(Rune.IsLetterOrDigit)
            .Select(Rune.ToUpperInvariant)
            .ToArray();
        int left = 0, right = values.Length - 1;
        while (left < right)
        {
            if (values[left++] != values[right--]) return false;
        }
        return true;
    }
}

复杂度： 时间 O(n)，额外空间 O(n)。

边界用例： 空字符串；只有符号；补充平面字符；大小写映射。

面试追问：

• 如果输入只保证 ASCII，如何把额外空间降为 O(1)？

解题思路： 按 Rune 增减频次，出现负数或最终非零时不匹配。

不变量： 字典表示 first 已扫描部分减去 second 已扫描部分的频次差。

public static class AlgCode018Solution
{
    public static bool Solve(string first, string second)
    {
        var counts = new Dictionary<Rune, int>();
        foreach (Rune value in first.EnumerateRunes())
            counts[value] = counts.GetValueOrDefault(value) + 1;
        foreach (Rune value in second.EnumerateRunes())
        {
            int next = counts.GetValueOrDefault(value) - 1;
            if (next < 0) return false;
            counts[value] = next;
        }
        return counts.Values.All(count => count == 0);
    }
}

复杂度： 平均时间 O(n+m)，额外空间 O(k)。

边界用例： 空字符串；重复字符；代理项；大小写不同。

面试追问：

• 如果字符集严格限制为小写英文字母，可以换成什么结构？

解题思路： 第一次扫描统计 char 频次，第二次扫描返回首个频次为一的位置。

不变量： 第二次扫描时字典已经包含完整输入的频次。

public static class AlgCode019Solution
{
    public static int Solve(string text)
    {
        var counts = new Dictionary<char, int>();
        foreach (char value in text)
            counts[value] = counts.GetValueOrDefault(value) + 1;
        for (int index = 0; index < text.Length; index++)
            if (counts[text[index]] == 1) return index;
        return -1;
    }
}

复杂度： 时间 O(n)，额外空间 O(k)。

边界用例： 空字符串；全部重复；返回值是 UTF-16 下标而非文本元素下标。

面试追问：

• 如果需要返回 Rune 序号，数据结构和遍历方式如何调整？

解题思路： 逐列比较所有字符串，第一次不一致时结束。

不变量： [0,index) 是所有已检查字符串的公共前缀。

public static class AlgCode020Solution
{
    public static string Solve(string[] values)
    {
        if (values.Length == 0) return string.Empty;
        string first = values[0];
        for (int index = 0; index < first.Length; index++)
        {
            char expected = first[index];
            for (int item = 1; item < values.Length; item++)
            {
                if (index >= values[item].Length ||
                    values[item][index] != expected)
                    return first[..index];
            }
        }
        return first;
    }
}

复杂度： 时间 O(总字符数)，额外空间 O(1) 不计返回值。

边界用例： 空数组；包含空字符串；完全相同；仅按 UTF-16 代码单元。

面试追问：

• 如果字符串数量巨大且可并行读取，可以怎样分治合并前缀？

解题思路： 按空白提取单词，逆序写入 StringBuilder。

不变量： 构建器始终包含已经处理的尾部单词且分隔符规范。

public static class AlgCode021Solution
{
    public static string Solve(string text)
    {
        var words = new List<string>();
        int index = 0;
        while (index < text.Length)
        {
            while (index < text.Length && char.IsWhiteSpace(text[index])) index++;
            int start = index;
            while (index < text.Length && !char.IsWhiteSpace(text[index])) index++;
            if (start < index) words.Add(text[start..index]);
        }
        words.Reverse();
        return string.Join(' ', words);
    }
}

复杂度： 时间 O(n)，额外空间 O(n)。

边界用例： 空字符串；全部空白；单个单词；多种空白字符。

面试追问：

• 如果输入是可修改字符数组，如何原地处理 ASCII 空格？

解题思路： 读指针识别连续段，写指针写字符和计数字符。

不变量： [0,write) 是所有已完成连续段的压缩结果。

public static class AlgCode022Solution
{
    public static int Solve(char[] chars)
    {
        int read = 0, write = 0;
        while (read < chars.Length)
        {
            char value = chars[read];
            int start = read;
            while (read < chars.Length && chars[read] == value) read++;
            chars[write++] = value;
            int count = read - start;
            if (count > 1)
            {
                foreach (char digit in count.ToString())
                    chars[write++] = digit;
            }
        }
        return write;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)；计数字符总量受输入长度约束。

边界用例： 空数组；没有重复；连续次数超过九。

面试追问：

• 为什么计数转字符串不会让额外空间随 n 线性增长？

解题思路： 为每个字符串构造 26 个频次组成的稳定键。

不变量： 键相同当且仅当两个字符串的每个字母频次相同。

public static class AlgCode023Solution
{
    public static string[][] Solve(string[] values)
    {
        var groups = new Dictionary<string, List<string>>(StringComparer.Ordinal);
        foreach (string value in values)
        {
            var counts = new int[26];
            foreach (char item in value) counts[item - 'a']++;
            string key = string.Join('#', counts);
            if (!groups.TryGetValue(key, out List<string>? group))
            {
                group = [];
                groups[key] = group;
            }
            group.Add(value);
        }
        return groups.Values.Select(group => group.ToArray()).ToArray();
    }
}

复杂度： 时间 O(总字符数)，额外空间 O(总字符数)。

边界用例： 空输入；空字符串；重复字符串；结果组顺序不作要求。

面试追问：

• 开放 Unicode 字符集后，键应如何表示？

解题思路： 逐段去除前导零，先比有效长度，再做序号比较。

不变量： 每轮之前的所有版本段数值相等。

public static class AlgCode024Solution
{
    public static int Solve(string first, string second)
    {
        string[] left = first.Split('.');
        string[] right = second.Split('.');
        int count = Math.Max(left.Length, right.Length);
        for (int index = 0; index < count; index++)
        {
            string a = Normalize(index < left.Length ? left[index] : "0");
            string b = Normalize(index < right.Length ? right[index] : "0");
            if (a.Length != b.Length) return a.Length.CompareTo(b.Length);
            int comparison = string.CompareOrdinal(a, b);
            if (comparison != 0) return Math.Sign(comparison);
        }
        return 0;
    }
    
    private static string Normalize(string value)
    {
        int index = 0;
        while (index < value.Length - 1 && value[index] == '0') index++;
        return value.Length == 0 ? "0" : value[index..];
    }
}

复杂度： 时间 O(n+m)，额外空间 O(n+m)。

边界用例： 空段；全部为零；数字段超过 long；段数不同。

面试追问：

• 如何改为不使用 Split 的单次扫描以减少分配？