Given list of Strings, task is to add a space before sequence which begin with capital letters.
Input : test_list = [“gfgBest”, “forGeeks”, “andComputerScienceStudents”]
Output : [‘gfg Best’, ‘for Geeks’, ‘and Computer Science Students’]
Explanation : Words segregated by Capitals.Input : test_list = [“ComputerScienceStudentsLoveGfg”]
Output : [‘Computer Science Students Love Gfg’]
Explanation : Words segregated by Capitals.
Method #1 : Using loop + join()
This is one of the ways in which this task can be performed. In this, we perform the task of iterating all the strings and then all the characters before adding space using loop in brute force manner. The isupper() is used to check for capital character.
Python3
# Python3 code to demonstrate working of # Add Space between Potential Words# Using loop + join()# initializing listtest_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list))res = []# loop to iterate all strings for ele in test_list: temp = [[]] for char in ele: # checking for upper case character if char.isupper(): temp.append([]) # appending character at latest list temp[-1].append(char) # joining lists after adding space res.append(' '.join(''.join(ele) for ele in temp))# printing result print("The space added list of strings : " + str(res)) |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings : ['gfg Best', 'for Geeks', 'and Computer Science']
The time complexity of the code is O(nm), where n is the number of strings in the list and m is the average length of the strings. The reason for this is that for each string in the list, the code needs to iterate through its characters and check if it is an upper case character. This takes O(m) time for each string.
The space complexity is O(nm) because of the use of multiple lists to store intermediate results.
Method #2 : Using regex() + list comprehension
The combination of above functions can also be used to solve this problem. In this we employ regex code to check for upper case letters and perform space addition and joining using list comprehension.
Python3
# Python3 code to demonstrate working of # Add Space between Potential Words# Using regex() + list comprehensionimport re# initializing listtest_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list))# using regex() to perform task res = [re.sub(r"(\w)([A-Z])", r"\1 \2", ele) for ele in test_list]# printing result print("The space added list of strings : " + str(res)) |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings : ['gfg Best', 'for Geeks', 'and Computer Science']
Time Complexity: O(n) where n is the number of elements in the list “test_list”. The re.sub() function is used to perform the task and it takes O(n) time.
Auxiliary Space: O(n) where n is the number of elements in the list “test_list”. The re.sub() function creates a new string for each element in the list and hence consumes O(n) space.
Method #3 : Using isupper() and replace() methods
The combination of above functions can also be used to solve this problem. In this we check for any uppercase character using isupper() function and then add an additional space with the use of replace() function.
Python3
# Python3 code to demonstrate working of# Add Space between Potential Words# initializing listtest_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list))res = []for i in test_list: for j in i: if(j.isupper()): i = i.replace(j, " "+j) res.append(i)# printing resultprint("The space added list of strings : " + str(res)) |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings : ['gfg Best', 'for Geeks', 'and Computer Science']
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n) where n is the number of elements in the list “test_list”.
Method #4 : Using loop, without any builtin methods
Python3
# Python3 code to demonstrate working of# Add Space between Potential Words# initializing listtest_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list))res = []alphabets="ABCDEFGHIJKLMNOPQRSTUVWXYZ"for i in test_list: s="" for j in i: if(j in alphabets): s+= " "+j else: s+=j res.append(s)# printing resultprint("The space added list of strings : " + str(res)) |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings : ['gfg Best', 'for Geeks', 'and Computer Science']
Time Complexity : O(N)
Auxiliary Space : O(N)
Method #5 : Using add_space():
Python3
import redef add_space(strings): return [re.sub(r'([A-Z][a-z]+)', r' \1', ele) for ele in strings]test_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list)) result = add_space(test_list)print("The space added list of strings:", result)#This code is contributed by Jyothi pinjala |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings: ['gfg Best', 'for Geeks', 'and Computer Science']
Time Complexity : O(N^2)
Auxiliary Space : O(N)
Method 6 : using regular expressions and the re module.
step-by-step approach:
- Import the re module.
- Define a regular expression pattern to match one or more uppercase letters ([A-Z]+) followed by one or more lowercase letters ([a-z]+), separated by zero or more non-alphabetic characters ([^a-zA-Z]*).
- Define a function add_space_regex(s) that uses the re.sub() method to replace all occurrences of the pattern with a space followed by the matched string (i.e., the potential word).
- Define a list comprehension that applies the add_space_regex() function to each element of the input list test_list to obtain the list of spaced strings.
- Print the original list and the list of spaced strings.
Python3
import re# initializing listtest_list = ["gfgBest", "forGeeks", "andComputerScience"]# printing original listprint("The original list : " + str(test_list))# define regular expression patternpattern = r'[A-Z]+[a-z]+[^a-zA-Z]*'# define function to add spaces using regexdef add_space_regex(s): return re.sub(pattern, r' \g<0>', s).strip()# apply function to each element of the list using list comprehensionres = [add_space_regex(s) for s in test_list]# printing resultprint("The space added list of strings : " + str(res)) |
The original list : ['gfgBest', 'forGeeks', 'andComputerScience'] The space added list of strings : ['gfg Best', 'for Geeks', 'and Computer Science']
The time complexity of this approach is O(nm), where n is the number of strings in the input list and m is the maximum length of a string in the list.
The auxiliary space complexity is O(m), for storing the output list of spaced strings.
METHOD 7:Using defaultdict
APPROACH:
This program takes an original list of strings as input and adds spaces between the potential words. The output is a modified list of strings.
ALGORITHM:
1.Iterate through each word in the original list
2.For each character in the word, check if it is uppercase
3.If it is uppercase, add a space to the previous character index in a defaultdict
4.Concatenate the values of the defaultdict and append it to the modified list
5.Print the modified list
Python3
from collections import defaultdictoriginal_list = ['gfgBest', 'forGeeks', 'andComputerScience']modified_list = []for word in original_list: d = defaultdict(str) for i, c in enumerate(word): if c.isupper(): d[i] += ' ' d[i] += c modified_list.append(''.join(d.values()))print("The modified list:", modified_list) |
The modified list: ['gfg Best', 'for Geeks', 'and Computer Science']
Time complexity: O(n*m) where n is the length of the original list and m is the average length of each word in the list.
Space complexity: O(n*m) since a defaultdict is created for each word in the list, and each defaultdict may store multiple characters.
