【大厂面试真题】系列，带你攻克大厂面试真题，秒变offer收割机！

?今日问题：实现一个string的indexof方法，给出时空复杂度估计

??一起看看文心快码Baidu Comate给出的答案吧！如果这个问题你也会，也可以在评论区写出你的答案哦～

@comate

下面是一个简单的indexOf方法的实现，该方法用于在字符串中查找子字符串首次出现的位置。如果找到子字符串，则返回其开始的索引；如果未找到，则返回-1。
def indexOf(main_str, sub_str):
    if not main_str or not sub_str:
        return -1
    
    main_length = len(main_str)
    sub_length = len(sub_str)
    
    # 遍历主字符串
    for i in range(main_length - sub_length + 1):
        # 检查子字符串是否匹配
        if main_str[i:i + sub_length] == sub_str:
            return i  # 返回匹配的起始索引
    
    return -1  # 如果未找到匹配，则返回-1
    时间复杂度分析：
最好情况：如果子字符串在主字符串的开头就找到，那么时间复杂度是O(sub_length)，因为只需要进行一次子字符串长度的比较。

最坏情况：如果子字符串不存在于主字符串中，或者存在于主字符串的末尾，那么需要遍历整个主字符串并进行多次子字符串长度的比较。因此，时间复杂度是O((main_length - sub_length + 1) * sub_length)。在大多数情况下，可以简化为O(main_length * sub_length)。

空间复杂度分析：
该算法仅使用了几个变量来存储字符串的长度和循环的索引，没有使用额外的数据结构。因此，空间复杂度是O(1)，表示常量级别的额外空间。
综上所述，这个indexOf方法的时间复杂度在最坏情况下是O(main_length * sub_length)，空间复杂度是O(1)。如果需要处理非常大的字符串或者对性能有较高要求，可以考虑使用更高效的字符串匹配算法，例如KMP算法或Boyer-Moore算法。