题解 | #BFS#_牛客博客

题目链接

BFS

题目描述

这道题是一个有趣的文字游戏，将 "BFS" 定义为 "Bob First Search"。任务是在给定的字符串中，从前向后查找子串 "Bob" 第一次出现的位置，查找过程不区分大小写。

输入描述:

输入一个不含空格的字符串，长度在 3 到 1000 之间。

输出描述:

输出子串 "Bob"（不区分大小写）第一次出现的起始下标（从 0 开始）。
如果子串从未出现，则输出 -1。

示例:

输入: Bobob
输出: 0 (在索引0处匹配到 "Bob")
输入: bobby
输出: 0 (在索引0处匹配到 "bob")
输入: body
输出: -1 (未找到匹配)

解题思路

解决这个问题的核心是进行一次不区分大小写的子串查找。最简单高效的方法是利用大多数语言提供的内置字符串函数。

思路一：转换为统一大小写后查找 (推荐)

这是最直接、最不容易出错的方法。既然比较时不区分大小写，我们干脆就把原字符串和目标子串都转换成同一种大小写（通常是全小写），问题就退化成了一个标准的、区分大小写的子串查找问题。

读取输入: 读取原始字符串 S。
转换为小写: 创建一个新的字符串 s_lower，它是原始字符串 S 的全小写版本。
查找子串: 在 s_lower 上，使用内置的 find 或 indexOf 方法查找子串 "bob" 第一次出现的位置。
输出结果:
- 这些内置函数在找到子串时，会返回其起始索引。
- 如果未找到，它们通常会返回 -1 (或在 C++ 中是 std::string::npos)。
- 这个返回值恰好与题目要求的输出格式完全一致，所以我们可以直接打印该函数的返回值。

思路二：手动滑动窗口比较

这是一个更底层的实现方法，不依赖高级的 find 函数。

读取输入: 读取原始字符串 S。
遍历: 使用一个循环，索引 i 从 0 遍历到 S.length() - 3。这个 i 将是潜在的匹配起始位置。
逐字符比较: 在每个位置 i，我们检查从该位置开始的三个字符 S[i], S[i+1], S[i+2] 是否在不区分大小写的情况下分别等于 'b', 'o', 'b'。
- 例如，检查 tolower(S[i]) == 'b', tolower(S[i+1]) == 'o', tolower(S[i+2]) == 'b'。
找到即停: 如果在某个索引 i 处，这三个字符都匹配成功，那么 i 就是我们想要的答案。立即打印 i 并终止程序。
未找到: 如果循环结束后仍未找到匹配，说明子串不存在，此时打印 -1。

考虑到代码的简洁性和可读性，思路一是解决此问题的最佳实践。

代码

c++
java
python

#include <iostream>
#include <string>
#include <algorithm> // for std::transform
#include <cctype>    // for std::tolower

using namespace std;

int main() {
    string s;
    cin >> s;
    
    // 1. 创建一个新字符串并转换为小写
    string s_lower = s;
    transform(s_lower.begin(), s_lower.end(), s_lower.begin(),
                   ::tolower);
    
    // 2. 在小写字符串中查找 "bob"
    size_t pos = s_lower.find("bob");
    
    // 3. 根据结果输出
    if (pos != string::npos) {
        cout << pos << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        // 1. 将原字符串转换为小写
        String sLower = s.toLowerCase();
        
        // 2. 调用 indexOf 方法查找，其返回值直接符合题目要求
        int index = sLower.indexOf("bob");
        
        System.out.println(index);
    }
}

# 读取输入字符串
s = input()

# 1. 将原字符串转换为小写
s_lower = s.lower()

# 2. 调用 find 方法查找，其返回值直接符合题目要求
# str.find() 如果找不到子串，会返回 -1
index = s_lower.find("bob")

print(index)

算法及复杂度

算法: 字符串查找。
时间复杂度: $\mathcal{O}(L)$ ，其中 L 是输入字符串的长度。将字符串转换为小写需要 $\mathcal{O}(L)$ 的时间。标准库中的子串查找算法（如 find, indexOf）在通常情况下的平均时间复杂度也是 $\mathcal{O}(L)$ 。
空间复杂度: $\mathcal{O}(L)$ 。因为我们需要创建一个新的字符串来存储原始字符串的小写版本。