Sometimes, while working with Python Strings, we can have a problem in which we need to construct strings with a single space at every possible word ending. This kind of application can occur in domains in which we need to perform testing. Let us discuss certain ways in which this task can be performed.
Method #1: Using loop + join()
This is a brute-force way in which this task can be performed. In this, we perform the task of forming all possible joins using join() and the task of iterating through all strings using a loop.
Python3
# Python3 code to demonstrate working of# All possible space joins in String# Using loop + join()# Initializing stringtest_str = 'Geeksforneveropen is best forneveropen'# printing original stringprint("The original string is : " + str(test_str))# All possible space joins in String# Using loop + join()res = []temp = test_str.split(' ')strt_idx = 0lst_idx = len(temp)for idx in range(len(temp)-1): frst_wrd = "".join(temp[strt_idx: idx + 1]) scnd_wrd = "".join(temp[idx + 1: lst_idx]) res.append(frst_wrd + " " + scnd_wrd)# Printing resultprint("All possible spaces List : " + str(res)) |
The original string is : Geeksforneveropen is best forneveropen All possible spaces List : [‘Geeksforneveropen isbestforneveropen’, ‘Geeksforneveropenis bestforneveropen’, ‘Geeksforneveropenisbest forneveropen’, ‘Geeksforneveropenisbestforneveropen’]
Time Complexity: O(n2) -> (loop + join)
Auxiliary Space: O(n)
Method #2: Using enumerate() + join() + combinations()
A combination of the above methods can be used to perform this task. In this, we perform the task of extracting combinations using combinations(). This prints all combinations of all occurrences of spaces rather than just one as in the above method.
Python3
# Python3 code to demonstrate working of# All possible space joins in String# Using enumerate() + join() + combinations()import itertools# initializing stringtest_str = 'Geeksforneveropen is best forneveropen'# printing original stringprint("The original string is : " + str(test_str))# All possible space joins in String# Using enumerate() + join() + combinations()res = []temp = test_str.split(' ')N = range(len(temp) - 1)for idx in N: for sub in itertools.combinations(N, idx + 1): temp1 = [val + " " if i in sub else val for i, val in enumerate(temp)] temp2 = "".join(temp1) res.append(temp2)# Printing resultprint("All possible spaces List : " + str(res)) |
The original string is : Geeksforneveropen is best forneveropen All possible spaces List : [‘Geeksforneveropen isbestforneveropen’, ‘Geeksforneveropenis bestforneveropen’, ‘Geeksforneveropenisbest forneveropen’, ‘Geeksforneveropenisbestforneveropen’, ‘Geeksforneveropen is bestforneveropen’, ‘Geeksforneveropen isbest forneveropen’, ‘Geeksforneveropen isbestforneveropen’, ‘Geeksforneveropenis best forneveropen’, ‘Geeksforneveropenis bestforneveropen’, ‘Geeksforneveropenisbest forneveropen’, ‘Geeksforneveropen is best forneveropen’, ‘Geeksforneveropen is bestforneveropen’, ‘Geeksforneveropen isbest forneveropen’, ‘Geeksforneveropenis best forneveropen’, ‘Geeksforneveropen is best forneveropen’]
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method#3: Recursive approach
Steps:
- Define a recursive function named all_possible_spaces that takes a string s and a current index i as input.
- If i is equal to the length of s, return an empty list.
- If i is equal to the last index of s, return a list containing s as the only element.
- Define a list named result.
- For each index j greater than or equal to i and less than the length of s:
- Define a variable named left as s from i to j and a variable right as s from j+1 to the end.
- Recursively call the all_possible_spaces to function on right with the current index as i+1.
- For each element in the list returned by the recursive call, append left + ‘ ‘ + element to the result list.
- Return the result list.
- Call the all_possible_spaces() function on the input string with an initial index of 0.
Python3
# Python program for the above approach# Function to find the list of all possible# spaces in the stringdef all_possible_spaces(s, i): # Base Case if i == len(s): return [] if i == len(s)-1: return [s] result = [] for j in range(i, len(s)): left = s[i:j+1] right = s[j+1:] # Recursive Call for sub in all_possible_spaces(right, i+1): result.append(left + ' ' + sub) return result# Driver Codes = 'Geeksforneveropen is best forneveropen'# Printing possible space in listprint('All possible spaces List :', all_possible_spaces(s, 0)) |
...g eeks', 'Geeksforneveropen is est f g eeks', 'Geeksforneveropen is est fo g eeks', 'Geeksforneveropen is est for ge eks', 'Geeksforneveropen is b s for g eeks', 'Geeksforneveropen is b st or g eeks', 'Geeksforneveropen is b st r g eeks', 'Geeksforneveropen is b st f g eeks', 'Geeksforneveropen is b st fo g eeks', 'Geeksforneveropen is b st for ge eks', 'Geeksforneveropen is be t or g eeks', 'Geeksforneveropen is be t r g eeks', 'Geeksforneveropen is be t f g eeks', 'Geeksforneveropen is be t fo g eeks', 'Geeksforneveropen is be t for ge eks', 'Geeksforneveropen is bes r g eeks', 'Geeksforneveropen is bes f g eeks', 'Geeksforneveropen is bes fo g eeks', 'Geeksforneveropen is bes for ge eks', 'Geeksforneveropen is best f g eeks', 'Geeksforneveropen is best fo g eeks', 'Geeksforneveropen is best for ge eks', 'Geeksforneveropen is best o g eeks', 'Geeksforneveropen is best or ge eks', 'Geeksforneveropen is best f r ge eks', 'Geeksforneveropen is best fo ge eks', 'Geeksforneveropen is best for ge eks', 'Geeksforneveropen is best for e eks', 'Geeksforneveropen is best for gee ks']
Time Complexity: O(2n), where n is the number of spaces in the input string. This is the worst-case time complexity when all possible combinations of spaces are considered.
Auxiliary Space: O(2n), where n is the number of spaces in the input string. This is the worst-case space complexity when all possible combinations of spaces are considered.
Method #5: Using itertools.product()
In this approach, we use itertools.product() function to generate all possible combinations of words in the input string. We then join each combination using a space and add it to a list, which is returned as the output.
Python3
import itertools# initializing stringtest_str = 'Geeksforneveropen is best forneveropen'# printing original stringprint("The original string is : " + str(test_str))# All possible space joins in String# Using itertools.product()words = test_str.split()res = [' '.join(combo) for i in range(1, len(words)+1) for combo in itertools.product(words, repeat=i)]# printing resultprint("All possible spaces List : " + str(res)) |
...eeksneveropen forneveropen Geeksforneveropen', 'neveropenneveropen forneveropen is', 'neveropenneveropen forneveropen best', 'neveropenneveropen forneveropen for', 'neveropenneveropen forneveropenneveropen', 'neveropenneveropenneveropen Geeksforneveropen Geeksforneveropen', 'neveropenneveropenneveropen Geeksforneveropen is', 'neveropenneveropenneveropen Geeksforneveropen best', 'neveropenneveropenneveropen Geeksforneveropen for', 'neveropenneveropenneveropen Geeksforneveropenneveropen', 'neveropenneveropenneveropen is Geeksforneveropen', 'neveropenneveropenneveropen is is', 'neveropenneveropenneveropen is best', 'neveropenneveropenneveropen is for', 'neveropenneveropenneveropen isneveropen', 'neveropenneveropenneveropen best Geeksforneveropen', 'neveropenneveropenneveropen best is', 'neveropenneveropenneveropen best best', 'neveropenneveropenneveropen best for', 'neveropenneveropenneveropen bestneveropen', 'neveropenneveropenneveropen for Geeksforneveropen', 'neveropenneveropenneveropen for is', 'neveropenneveropenneveropen for best', 'neveropenneveropenneveropen for for', 'neveropenneveropenneveropen forneveropen', 'neveropenneveropenneveropenneveropen Geeksforneveropen', 'neveropenneveropenneveropenneveropen is', 'neveropenneveropenneveropenneveropen best', 'neveropenneveropenneveropenneveropen for', 'neveropenneveropenneveropenneveropenneveropen']
Time complexity: O(2^n), where n is the number of words in the input string.
Auxiliary space: O(2^n), since we store all possible combinations in a list.
Method#5 Using list comprehension and slicing
Approach:
- Initialize the input string test_str.
- Split the input string into words and store the words in a list of words.
- Initialize an empty list res to store all possible space joins of the words in words.
- Iterate through all possible split points i of the words in words using a range function.
- Generate a space join of the first i words and the remaining words after i.
- Append the generated space join to the list res.
- Print the original input string and the list of all possible space joins.
Python3
# Initializing input list test_str = 'Geeksforneveropen is best forneveropen'# split string into wordswords = test_str.split()# Generating all possible space joinsres = [f"{' '.join(words[:i])} {' '.join(words[i:])}" for i in range( 1, len(words))]# Print original stringprint("The original string is : " + str(test_str))# Print resultprint("All possible spaces List : " + str(res)) |
All possible spaces List : ['Geeksforneveropen is best forneveropen', 'Geeksforneveropen is best forneveropen', 'Geeksforneveropen is best forneveropen', 'Geeksforneveropen is best forneveropen']
Time complexity: O(n^2), where n is the number of words in the input string. This is because the program needs to iterate through all possible split points of the words and generate a space join for each split point.
Auxiliary space: O(n^2), where n is the number of words in the input string. This is because the program needs to store all possible space joins in the list res.
