实现一个string的indexof方法，给出时空复杂度估计

文心快码(BaiduComate)是基于百度文心大模型，在研发全流程全场景下为开发者提供辅助建议的智能代码助手。结合百度积累多年的编程现场大数据、外部优秀开源数据，可为开发者生成更符合实际研发场景的优秀代码，提升编码效率，释放“十倍”软件生产力。

如果您对【文心快码企业版】感兴趣，希望获取更多详细信息，👉点击进入企业服务咨询

我们会尽快安排专业人员与您取得联系！我们期待与您建立联系，为您的企业带来更高效、更智能的工作体验。

🔍【大厂面试真题】系列，带你攻克大厂面试真题，秒变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算法。

原文地址：https://blog.csdn.net/2401_86237385/article/details/143902845

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！