[LeetCode] 每日一题 2255. 统计是给定字符串前缀的字符串数目（简单遍历比较）

题目链接

https://leetcode.cn/problems/count-prefixes-of-a-given-string

题目描述

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s 前缀 的 字符串数目 。

一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例输入

示例 1

输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

示例 2

输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。

提示

• 1 <= words.length <= 1000

• 1 <= words[i].length, s.length <= 10

• words[i] 和 s 只 包含小写英文字母。

解题思路

这道题非常简单，基本思路就是直接遍历数组，逐个判断每个单词是否是字符串 s 的前缀。具体步骤是：

1. 遍历 words 数组，对每个单词 word，检查它是否是 s 的前缀。

2. 判断 word 的长度是否大于 s，如果是，直接返回 false。如果不是，逐个字符进行比较，确保 word 的每个字符都和 s 从头开始的字符一致

3. 最后返回符合条件的前缀的数量

我觉得这题唯一需要注意的就是读清楚题目要求，在我一开始写的时候，我把判断前缀的条件搞反了😂，搞清楚是 words[i] 是否是 s 的前缀，而不是反过来

代码实现

class Solution {
    public int countPrefixes(String[] words, String s) {
        int count = 0;
        for (String word : words) {
            if (check(word, s)) {
                count++;
            }
        }
        return count;
    }

    private boolean check(String word, String s) {
        if (word.length() > s.length()) {
            return false;
        }
        for (int i = 0; i < word.length(); i++) {
            if (s.charAt(i) != word.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是 words 数组的长度，m 是 s 的最大长度。对于每个 word，我们最多比较 word.length() 个字符，而 word.length() 最大为 s.length()，因此总的时间复杂度是 O(n * m)

• 空间复杂度：O(1)，我们只使用了常数空间，存储计数变量 count 和临时变量 word

总结

这道题的解法非常直观，简单的遍历与前缀比较就可以解决。最重要的是理解清楚题目要求，确保前缀判断是基于 s 字符串的，而不是反过来。遍历时，首先要检查 word 的长度是否符合条件，接着逐字符比较，最后统计符合条件的字符串数目

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。