Typically, the “find substring in string” problem could be efficiently solved by the Knuth–Morris–Pratt algorithm
Also, you can have detailed algorithm workthrough found here.
Interestingly, in Python, the str.find(‘substring’) is implemented by Boyer–Moore–Horspool algorithm, which is related to the KMP algorithm.
Time complexity: O(n + k)
RUntime: 13ms
Runtime: 13ms
Brutal algorithm in Python
This problem could also be solved brutal algorithms.
Time complexity: O(n^2)
Runtime: 38 ms
Note: the runtime looks okay just because leetcode’s unit test cases are simple.