Sometimes, while working with python strings, we can have a problem in which we need to test occurrence of substring. There is straight forward way to test this. But sometimes, we have a more specific problem in which we need to test if substring occurs at that particular position. Let’s discuss certain ways in which this task can be performed.
Method #1: Using loop This is brute method to solve this problem. In this we iterate the string and when index occur we test for substring characters simultaneously.
Python3
# Python3 code to demonstrate working of# Test if Substring occurs in specific position# Using loop# initializing stringtest_str = "Gfg is best"# printing original stringprint("The original string is : " + test_str)# initializing rangei, j = 7, 11# initializing substrsubstr = "best"# Test if Substring occurs in specific position# Using loopres = Truek = 0for idx in range(len(test_str)): if idx >= i and idx < j: if test_str[idx] != substr[k]: res = False break k = k + 1# printing resultprint("Does string contain substring at required position ? : " + str(res)) |
The original string is : Gfg is best Does string contain substring at required position ? : True
Time Complexity: O(n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(1), constant extra space is needed
Method #2: Using string slicing This is a one-liner way to perform this task. In this, we check the substring in string using string slicing.
Python3
# Python3 code to demonstrate working of# Test if Substring occurs in specific position# Using string slicing# initializing stringtest_str = "Gfg is best"# printing original stringprint("The original string is : " + test_str)# initializing rangei, j = 7, 11# initializing substrsubstr = "best"# Test if Substring occurs in specific position# Using string slicingres = test_str[i: j] == substr# printing resultprint("Does string contain substring at required position ? : " + str(res)) |
The original string is : Gfg is best Does string contain substring at required position ? : True
Method #3 : Using find() method
Python3
# Python3 code to demonstrate working of# Test if Substring occurs in specific position# initializing stringtest_str = "Gfg is best"# printing original stringprint("The original string is : " + test_str)# initializing rangei, j = 7, 11# initializing substrsubstr = "best"# Test if Substring occurs in specific position# Using string slicingres = Falseif(test_str.find(substr) == i): res = True# printing resultprint("Does string contain substring at required position ? : " + str(res)) |
The original string is : Gfg is best Does string contain substring at required position ? : True
Method#4: Using Recursive method.
Algorithm:
- Check if the ending index j is greater than the length of the input string test_str. If it is, return False, because the substring cannot exist outside the range of the input string.
- Check if the substring starting from index i and ending at index j is equal to the input substring substr. If it is, return True, because the substring has been found at the specified position.
- Otherwise, call the function recursively with the starting index incremented by 1 and the ending index incremented by 1, to check the next possible substring.
Python3
# Python3 code to demonstrate working of# Test if Substring occurs in specific positiondef substring_occurs_at_position(test_str, substr, i, j): if j > len(test_str): return False if test_str[i:j] == substr: return True return substring_occurs_at_position(test_str, substr, i+1, j+1)# initializing stringtest_str = "Gfg is best"# printing original stringprint("The original string is : " + test_str)# initializing rangei, j = 7, 11# initializing substrsubstr = "best"result = substring_occurs_at_position(test_str, substr, i, j)# printing resultprint("Does string contain substring at required position? ", result)#this code contributed by tvsk |
The original string is : Gfg is best Does string contain substring at required position? True
The time complexity of this function is O(n), where n is the length of the input string test_str. This is because in the worst case, the function will need to iterate over the entire string to find the substring.
The auxiliary space complexity of the function is O(1), because it does not use any extra space that is proportional to the size of the input. The function only uses a constant amount of space to store the input parameters and temporary variables.
Method #5: Using Regular Expression
Step-by-step approach:
- Import the re module.
- Define a regular expression pattern that matches the substring at the specific position in the string. The pattern should use the “^” character to anchor the search at the specific position and the “$” character to match the end of the string.
- Use the re.search() function to search for the regular expression pattern in the string.
- If a match is found, set the result to True, else set it to False.
- Print the result.
Python3
import re# initializing stringtest_str = "Gfg is best"# printing original stringprint("The original string is : " + test_str)# initializing rangei, j = 7, 11# initializing substrsubstr = "best"# Test if Substring occurs in specific position# Using regular expressionpattern = "^" + substr + "$"res = bool(re.search(pattern, test_str[i:j+1]))# printing resultprint("Does string contain substring at required position ? : " + str(res)) |
The original string is : Gfg is best Does string contain substring at required position ? : True
The time complexity of this program is O(1) because it uses a constant amount of time to compile the regular expression pattern and search for the pattern in the string.
The auxiliary space of this program is also O(1) because it uses a constant amount of memory to store the regular expression pattern and the result of the search operation.
