字符串遍历与统计

学习目标

本节学习字符串遍历与字符统计。

很多字符串问题都可以从遍历开始：逐个访问字符，记录信息，最后根据记录结果做判断。字符频率统计是最常见的例子，也是后续学习哈希表和字符串算法的重要基础。

遍历字符串

遍历字符串就是按顺序访问每个字符。

string text = "hello";

for (char ch : text) {
    cout << ch << endl;
}

String text = "hello";

for (int i = 0; i < text.length(); i++) {
    char ch = text.charAt(i);
    System.out.println(ch);
}

text = "hello"

for ch in text:
    print(ch)

string text = "hello";

foreach (char ch in text)
{
    Console.WriteLine(ch);
}

如果字符串长度是 $n$ ，遍历所有字符通常需要 $O(n)$ 时间。

统计字符出现次数

统计字符频率可以使用映射结构。这里先使用语言中的字典或映射工具，后续学习哈希表时会更深入理解它的原理。

unordered_map<char, int> count;

for (char ch : text) {
    count[ch]++;
}

Map<Character, Integer> count = new HashMap<>();

for (int i = 0; i < text.length(); i++) {
    char ch = text.charAt(i);
    count.put(ch, count.getOrDefault(ch, 0) + 1);
}

count = {}

for ch in text:
    count[ch] = count.get(ch, 0) + 1

Dictionary<char, int> count = new Dictionary<char, int>();

foreach (char ch in text)
{
    if (!count.ContainsKey(ch))
    {
        count[ch] = 0;
    }

    count[ch]++;
}

这段代码的核心是：每遇到一个字符，就把它的计数加 1。

如果字符串长度是 $n$ ，遍历过程是 $O(n)$ 。映射中存放的字符种类数量最多不会超过字符串长度，因此额外空间复杂度最多是 $O(n)$ 。

判断两个字符串是否由相同字符组成

字符计数可以解决很多问题。例如，判断两个字符串是否由相同字符组成，并且每个字符出现次数也相同。

bool sameCharacters(string a, string b) {
    if (a.size() != b.size()) {
        return false;
    }

    unordered_map<char, int> count;

    for (char ch : a) {
        count[ch]++;
    }

    for (char ch : b) {
        count[ch]--;

        if (count[ch] < 0) {
            return false;
        }
    }

    return true;
}

boolean sameCharacters(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    Map<Character, Integer> count = new HashMap<>();

    for (int i = 0; i < a.length(); i++) {
        char ch = a.charAt(i);
        count.put(ch, count.getOrDefault(ch, 0) + 1);
    }

    for (int i = 0; i < b.length(); i++) {
        char ch = b.charAt(i);
        count.put(ch, count.getOrDefault(ch, 0) - 1);

        if (count.get(ch) < 0) {
            return false;
        }
    }

    return true;
}

def same_characters(a, b):
    if len(a) != len(b):
        return False

    count = {}

    for ch in a:
        count[ch] = count.get(ch, 0) + 1

    for ch in b:
        count[ch] = count.get(ch, 0) - 1

        if count[ch] < 0:
            return False

    return True

bool SameCharacters(string a, string b)
{
    if (a.Length != b.Length)
    {
        return false;
    }

    Dictionary<char, int> count = new Dictionary<char, int>();

    foreach (char ch in a)
    {
        if (!count.ContainsKey(ch))
        {
            count[ch] = 0;
        }

        count[ch]++;
    }

    foreach (char ch in b)
    {
        if (!count.ContainsKey(ch))
        {
            return false;
        }

        count[ch]--;

        if (count[ch] < 0)
        {
            return false;
        }
    }

    return true;
}

这个例子体现了字符串统计的常见思路：先记录第一个字符串中的字符频率，再用第二个字符串抵消这些频率。如果某个字符不够抵消，说明两个字符串不匹配。

统计思想的价值

字符串统计问题的关键不在于代码长短，而在于把“字符出现情况”转化成可以比较的数据。

很多题目都可以使用类似思想：

判断是否存在重复字符。
找出第一个只出现一次的字符。
判断两个字符串是否是异位词。
统计每个字符出现频率。
根据字符频率重新组织字符串。

这些问题都会在后续哈希表学习中进一步展开。

本节小结

字符串遍历是处理字符串问题的基础操作，通常是 $O(n)$ 。

字符统计通过映射结构记录字符出现次数，可以解决大量文本分析和字符串判断问题。学习字符串时，要习惯把“文本问题”转化成“字符序列和频率信息”的问题。