Let us solve this general problem of finding if a particular piece of string is present in a larger string in different ways. This is a very common kind of problem every programmer comes across atleast once in his/her lifetime. This article gives various techniques to solve it.
Method 1: Using in operator The in operator is the most generic, fastest method to check for a substring, the power of in operator in python is very well known and is used in many operations across the entire language.
Python3
# Python 3 code to demonstrate # checking substring in string# using in operator# initializing string test_str = "Lazyroar"# using in to test# for substringprint ("Does for exists in Lazyroar ? : ")if "for" in test_str : print ("Yes, String found")else : print ("No, String not found") |
Output :
Does for exists in Lazyroar ? : Yes, String found
Time Complexity: O(1)
Auxiliary Space: O(1)
Method 2 : Using str.find() str.find() method is generally used to get the lowest index at which the string occurs, but also returns -1, if string is not present, hence if any value returns >= 0, string is present, else not present.
Python3
# Python 3 code to demonstrate # checking substring in string# using str.find()# initializing string test_str = "Lazyroar"# using str.find() to test# for substringres = test_str.find("for")if res >= 0: print ("for is present in Lazyroar")else : print ("for is not present in Lazyroar") |
Output :
for is present in Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3 : Using str.index() This method can be used to performs the similar task, but like str.find(), it doesn’t return a value, but a ValueError if string is not present, hence catching the exception is the way to check for string in substring.
Python3
# Python 3 code to demonstrate # checking substring in string# using str.index()# initializing string test_str = "Lazyroar"# using str.index() to test# for substringtry : res = test_str.index("forg") print ("forg exists in Lazyroar")except : print ("forg does not exists in Lazyroar") |
Output :
forg does not exists in Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 4 : Using operator.contains() This is lesser known method to check for substring in a string, this method is also effective in accomplishing this task of checking a string in a string.
Python3
# Python 3 code to demonstrate # checking substring in string# using operator.contains()import operator# initializing string test_str = "Lazyroar"# using operator.contains() to test# for substringif operator.contains(test_str, "for"): print ("for is present in Lazyroar")else : print ("for is not present in Lazyroar") |
Output :
for is present in Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(1)
Method#5: Using String.count() function: This function is used to count the presence of element is the string. We can use this function to check the existence of string in large string. If string exist in string then it return some number else it return 0.
Python3
# Python 3 code to demonstrate # checking substring in string# using String.count() # initializing string test_str = "Lazyroar"# Substring temp = "for"# using String.count to test# for substringans = test_str.count(temp)# Printing our resultif ans: print ("for is present in Lazyroar")else : print ("for is not present in Lazyroar") |
Output:
for is present in Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(1)
Method#6: Using re.search() function: re.search() function is used to search for an pattern in string. We can use sub-string as a pattern to search in string.
Python3
# Python 3 code to demonstrate # checking substring in string# using re.search() import re# initializing string test_str = "Lazyroar"# Substring temp = "forg"# using re.search to test# for substringans = re.search(temp, test_str)# Printing our resultif ans: print ("forg is present in Lazyroar")else : print ("forg is not present in Lazyroar") |
Output:
forg is not present in Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(1)
Method#7: Using list comprehension
Python3
s="Lazyroar for Lazyroar"s2="Lazyroar"print(["yes" if s2 in s else "no"]) |
['yes']
Time Complexity: O(1)
Auxiliary Space: O(1)
Method #8: using any() function : The any() function, which returns True if any element in the iterable is True.
Step by Step Algorithm :
- Initialize two variables: string to the given string and substring to the given substring.
- Use a for loop to iterate through all possible substrings of the given string that are of the same length as the given substring.
- Check if the current substring is equal to the given substring using the equality operator ==.
- If the current substring is equal to the given substring, print that the substring is present in the given string and exit the loop.
- If the loop completes without finding any substring that is equal to the given substring, print that the substring is not present in the given string.
Python3
string = "GeekforGeeks"substring = "for"if any(string[i:i+len(substring)] == substring for i in range(len(string)-len(substring)+1)): print("for is present in Lazyroar")else: print("for is not present in Lazyroar") |
for is present in Lazyroar
Complexity Analysis :
Time Complexity: O(n*m) where n is length of string and m is length of substring
This is because the code iterates through a sequence of integers generated by the range function that has length O(n-m), and for each integer in the sequence, the code checks if the corresponding substring of length m starting at that position is equal to the substring. This substring check takes O(m) time. So overall time complexity will be O((n-m)m) = O(n*m).
Auxiliary Space: O(1)
This is because we only use a few variables to store the input string, substring, and the boolean result of the check. The space used by these variables does not depend on the size of the input string or substring.
