检查是否所有 A 都在 B 之前

难度: Easy

给你一个仅由字符 'a' 和 'b' 组成的字符串 s 。如果字符串中每个 'a' 都出现在每个 'b' 之前，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aaabbb"
输出：true
解释：
'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

示例 2：

输入：s = "abab"
输出：false
解释：
存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false 。

示例 3：

输入：s = "bbb"
输出：true
解释：
不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

提示：

1 <= s.length <= 100
s[i] 为 'a' 或 'b'

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def checkString(self, s: str) -> bool:
        for i in range(len(s)):
            if s[i] == 'a':
                for j in range(i):#[0,i-1]
                    if s[j] == 'b':
                        return False
        return True

Explain

该题解采用了一种直观的方法来检查字符串中的字符顺序。它遍历字符串中的每个字符，当遇到字符 'a' 时，它再次从字符串的开始到当前字符的前一个位置进行遍历，检查是否存在字符 'b'。如果在任何一个 'a' 之前找到了 'b'，则直接返回 false，表示不满足所有 'a' 都在 'b' 之前的条件。如果整个字符串遍历完成后没有发现这种情况，则返回 true。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def checkString(self, s: str) -> bool:
        # 遍历字符串中的每个字符
        for i in range(len(s)):
            if s[i] == 'a': # 当前字符是 'a'
                # 检查从字符串开始到当前 'a' 之前是否有 'b'
                for j in range(i): # [0, i-1]
                    if s[j] == 'b':
                        return False # 发现 'b' 在 'a' 之前，返回 False
        return True # 所有 'a' 都在 'b' 之前

Explore

该算法设计的初衷是确保每个出现的'a'之前没有任何一个'b'。如果只检查'a'前一个位置，则不能保证在更早位置上没有出现过'b'，这样会导致算法错误地认为所有的'a'都在'b'之前。例如，在字符串'baa'中，第二个'a'前一个位置是另一个'a'，这样的检查会错误地返回true。因此，算法需要从头开始检查至该'a'之前的所有位置，确保这之前没有任何一个'b'。

是的，该算法已经实现了在确定结果为false后立即停止检查的逻辑。在内层循环中，如果发现有'b'在'a'之前，会立即返回false，结束函数执行。这样的设计有效地减少了不必要的计算，尽快给出判断结果。

如果输入字符串非常长，该算法的性能可能会受到影响，因为它在最坏情况下的时间复杂度为O(n^2)。对于每个'a'，算法都会从头开始检查至该'a'之前的所有字符，导致大量重复的检查，特别是当字符串中'a'的数量较多时。性能优化可以考虑使用一种更高效的方法，例如单次遍历字符串，使用一个标记记录是否已经遇到过'b'，这样可以将时间复杂度降低到O(n)。内存方面，当前算法只使用了常数额外空间，因此内存管理上不需要特别措施。