What is Python – All possible space joins in String?

In this article, we will learn Python – All possible space joins in String,This free Python tutorial for complete beginners will help you learn Python from scratch.

Python – All possible space joins in String️‍🔥

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 string
test_str = 'w3wiki is best for Beginner'
 
# printing original string
print("The original string is : " + str(test_str))
 
# All possible space joins in String
# Using loop + join()
res = []
 
temp = test_str.split(' ')
strt_idx = 0
lst_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 result
print("All possible spaces List : " + str(res))

Output :

The original string is : w3wiki is best for Beginner All possible spaces List : [‘w3wiki isbestforBeginner’, ‘w3wikiis bestforBeginner’, ‘w3wikiisbest forBeginner’, ‘w3wikiisbestfor Beginner’]

Time Complexity: O(n²) -> (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 string
test_str = 'w3wiki is best for Beginner'
 
# printing original string
print("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 result
print("All possible spaces List : " + str(res))

Output :

The original string is : w3wiki is best for Beginner All possible spaces List : [‘w3wiki isbestforBeginner’, ‘w3wikiis bestforBeginner’, ‘w3wikiisbest forBeginner’, ‘w3wikiisbestfor Beginner’, ‘w3wiki is bestforBeginner’, ‘w3wiki isbest forBeginner’, ‘w3wiki isbestfor Beginner’, ‘w3wikiis best forBeginner’, ‘w3wikiis bestfor Beginner’, ‘w3wikiisbest for Beginner’, ‘w3wiki is best forBeginner’, ‘w3wiki is bestfor Beginner’, ‘w3wiki isbest for Beginner’, ‘w3wikiis best for Beginner’, ‘w3wiki is best for Beginner’]

Time Complexity: O(n²)
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.
1. If i is equal to the length of s, return an empty list.
2. If i is equal to the last index of s, return a list containing s as the only element.
3. Define a list named result.
4. 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.
5. 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 string
def 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 Code
s = 'w3wiki is best for Beginner'
 
# Printing possible space in list
print('All possible spaces List :', all_possible_spaces(s, 0))

Output

...g eeks', 'w3wiki is  est f  g eeks', 'w3wiki is  est fo g eeks', 'w3wiki is  est for ge eks', 'w3wiki is b s for g eeks', 'w3wiki is b st or g eeks', 'w3wiki is b st  r g eeks', 'w3wiki is b st f  g eeks', 'w3wiki is b st fo g eeks', 'w3wiki is b st for ge eks', 'w3wiki is be t or g eeks', 'w3wiki is be t  r g eeks', 'w3wiki is be t f  g eeks', 'w3wiki is be t fo g eeks', 'w3wiki is be t for ge eks', 'w3wiki is bes   r g eeks', 'w3wiki is bes  f  g eeks', 'w3wiki is bes  fo g eeks', 'w3wiki is bes  for ge eks', 'w3wiki is best f  g eeks', 'w3wiki is best fo g eeks', 'w3wiki is best for ge eks', 'w3wiki is best  o g eeks', 'w3wiki is best  or ge eks', 'w3wiki is best f r ge eks', 'w3wiki is best fo  ge eks', 'w3wiki is best for ge eks', 'w3wiki is best for  e eks', 'w3wiki is best for gee ks']

Time Complexity: O(2ⁿ), 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(2ⁿ), 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 string
test_str = 'w3wiki is best for Beginner'
 
# printing original string
print("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 result
print("All possible spaces List : " + str(res))

Output

...eeks Beginner for Beginner w3wiki', 'Beginner Beginner for Beginner is', 'Beginner Beginner for Beginner best', 'Beginner Beginner for Beginner for', 'Beginner Beginner for Beginner Beginner', 'Beginner Beginner Beginner w3wiki w3wiki', 'Beginner Beginner Beginner w3wiki is', 'Beginner Beginner Beginner w3wiki best', 'Beginner Beginner Beginner w3wiki for', 'Beginner Beginner Beginner w3wiki Beginner', 'Beginner Beginner Beginner is w3wiki', 'Beginner Beginner Beginner is is', 'Beginner Beginner Beginner is best', 'Beginner Beginner Beginner is for', 'Beginner Beginner Beginner is Beginner', 'Beginner Beginner Beginner best w3wiki', 'Beginner Beginner Beginner best is', 'Beginner Beginner Beginner best best', 'Beginner Beginner Beginner best for', 'Beginner Beginner Beginner best Beginner', 'Beginner Beginner Beginner for w3wiki', 'Beginner Beginner Beginner for is', 'Beginner Beginner Beginner for best', 'Beginner Beginner Beginner for for', 'Beginner Beginner Beginner for Beginner', 'Beginner Beginner Beginner Beginner w3wiki', 'Beginner Beginner Beginner Beginner is', 'Beginner Beginner Beginner Beginner best', 'Beginner Beginner Beginner Beginner for', 'Beginner Beginner Beginner Beginner Beginner']

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 = 'w3wiki is best for Beginner'
 
# split string into words
words = test_str.split()
 
# Generating all possible space joins
res = [f"{' '.join(words[:i])} {' '.join(words[i:])}" for i in range(
    1, len(words))]
 
# Print original string
print("The original string is : " + str(test_str))
 
# Print result
print("All possible spaces List : " + str(res))

Output

All possible spaces List : ['w3wiki is best for Beginner', 'w3wiki is best for Beginner', 'w3wiki is best for Beginner', 'w3wiki is best for Beginner']

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.