Easy

题目描述

给定一个字符串 s，其中每两个连续的竖线 '|' 被分组成一对。换句话说，第1个和第2个 '|' 组成一对，第3个和第4个 '|' 组成一对，以此类推。

返回 s 中 '*' 的数量，不包括每对 '|' 之间的 '*'。

注意每个 '|' 都恰好属于一对。

示例 1：

输入：s = "l|*e*et|c**o|*de|"
输出：2
解释：考虑的字符已标下划线："l|*e*et|c**o|*de|"。
第一对和第二个 '|' 之间的字符被排除在答案之外。
同样，第三个和第四个 '|' 之间的字符也被排除在答案之外。
有 2 个星号被考虑，因此返回 2。

示例 2：

输入：s = "iamprogrammer"
输出：0
解释：在这个例子中，s 中没有星号，因此返回 0。

示例 3：

输入：s = "yo|uar|e**|b|e***au|tifu|l"
输出：5
解释：考虑的字符已标下划线："yo|uar|e**|b|e***au|tifu|l"。有 5 个星号被考虑，因此返回 5。

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母、竖线 '|' 和星号 '*' 组成
  • s 包含偶数个竖线 '|'

解题思路

这道题的关键在于理解竖线的配对规则：第1个和第2个竖线为一对，第3个和第4个竖线为一对，以此类推。我们需要统计不在任何一对竖线之间的星号数量。

解题思路：

  1. 状态追踪法：遍历字符串，用一个布尔变量 inside 记录当前是否在竖线对内部

    • 遇到竖线时，切换 inside 状态
    • 遇到星号且不在竖线对内部时，计数器加1

  2. 计数器法：通过统计已遇到的竖线数量来判断状态

    • 竖线数量为奇数时表示在竖线对内部，偶数时表示在外部
    • 这种方法更直观，不需要额外的布尔变量

推荐使用状态追踪法，代码更简洁直观。时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int countAsterisks(string s) {
        int count = 0;
        bool inside = false;
        
        for (char c : s) {
            if (c == '|') {
                inside = !inside;
            } else if (c == '*' && !inside) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countAsterisks(self, s: str) -> int:
        count = 0
        inside = False
        
        for c in s:
            if c == '|':
                inside = not inside
            elif c == '*' and not inside:
                count += 1
                
        return count

public class Solution {
    public int CountAsterisks(string s) {
        int count = 0;
        bool inside = false;
        
        foreach (char c in s) {
            if (c == '|') {
                inside = !inside;
            } else if (c == '*' && !inside) {
                count++;
            }
        }
        
        return count;
    }
}

var countAsterisks = function(s) {
    let count = 0;
    let insidePair = false;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '|') {
            insidePair = !insidePair;
        } else if (s[i] === '*' && !insidePair) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串一次，其中 n 为字符串长度
空间复杂度O(1)只使用常数个额外变量