Python – Split String of list on K character

Sometimes while working with data, we can have a problem in which we need to perform split operation on Strings, and sometimes, we might also require to perform them into nested strings overall. Lets discuss certain ways in which this task can be performed. 

Method #1 : Using loop + split() The combination of above functionalities can be used to perform this task. In this, we iterate through each list string and perform a manual split and then add the new elements to that list using extend() using loop. 

The original list is : ['Gfg is best', 'for Geeks', 'Preparing']
The extended list after split strings : ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

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 new res list 

  Method #2 : Using join() + split() The combination of above functions can be used to perform this task. In this, we join split all the elements of list and then join each of them to make it split by K. 

The original list is : ['Gfg is best', 'for Geeks', 'Preparing']
The extended list after split strings : ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

Method #3 : Here is another approach using itertools.chain and str.split:

The extended list after split strings: ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

This approach uses itertools.chain to concatenate the output of str.split for each element in test_list. The s.split(K) operation returns a list of strings that were split from s using K as the delimiter. The itertools.chain function then concatenates the outputs from all iterations into a single list.

The time complexity of this approach is O(n), where n is the total number of characters in all elements of test_list. The space complexity is O(n) as well, since we need to store the output list in memory.

Method 4 : using List Comprehension.

step-by-step approach of the given code:

1. Initialize a list test_list with three string elements.
2. Initialize a string K with a space character.
3. Create a new list result using List Comprehension, which will store the resulting list of words after splitting the phrases.
4. The List Comprehension consists of two nested for-loops: the outer loop iterates over the phrases in test_list, and the inner loop iterates over the words in each phrase.
5. The split() method is called on each phrase, using the K string as the separator, which splits the phrase into a list of words.
6. The resulting list of words is flattened and stored in result.
7. The print() function is called to display the resulting list of words.

The extended list after split strings: ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

Time Complexity: O(N*M) where N is the number of phrases in the list and M is the average length of each phrase.

Auxiliary Space: O(N*M) to store the resulting list of words.

Method#5: Using Recursive method.

This implementation defines two functions: split_list_on_char and split_string_on_char. The first function takes a list of items and a character, and returns a new list where each string item in the original list has been split into a list of sub-items at the given character. The second function is a helper function that recursively splits a single string on the given character.

The split_string_on_char function works by finding the index of the given character in the string, and splitting the string into two parts: the left side before the character, and the right side after the character. It then recursively splits the right side until there are no more occurrences of the character, and concatenates the left side with the resulting list of sub-strings.

The split_list_on_char function simply applies the split_string_on_char function to each string item in the input list, and extends the result list with the resulting sub-items.

The extended list after split strings: ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

Time complexity: O(nm), where n is the length of the input list and m is the length of the longest string in the input list. This is because the code recursively splits each string in the input list into sub-strings at the given character, and the split operation takes O(m) time in the worst case.

Space complexity: O(nm), where n is the length of the input list and m is the length of the longest string in the input list. This is because the code creates a new list to store the resulting sub-strings, and the size of the list can be as large as the product of n and m if every string in the input list is the longest string and every character in each string is the given character. Additionally, the recursive calls to split_string_on_char can create a stack of up to O(m) frames in the worst case, as each recursive call adds a new frame to the stack.

Method#6: Using Reduce():
Algorithm:

1. Define a function split_string_on_char which takes a string and a separator character as inputs.
2. If the separator character is not present in the string, return a list with that string as the only element.
   Otherwise, find the index of the separator character in the string.
3. Split the string into two parts at that index – the left part and the right part.
4. Recursively call the split_string_on_char function on the right part, and add the left part to the beginning of the resulting list.
5. Return the resulting list.
6. Define a function split_list_on_char which takes a list of strings and a separator character as inputs.
7. Use the reduce function to apply the split_string_on_char function to each string in the list.
8. If the string is not a string (i.e., if it is some other type of object), just add it to the accumulated result list.
9. Return the accumulated result list.
    

The extended list after split strings: ['Gfg', 'is', 'best', 'for', 'Geeks', 'Preparing']

Time complexity:

The time complexity of the split_string_on_char function is O(n), where n is the length of the string.
The time complexity of the reduce function in the split_list_on_char function is O(n), where n is the length of the input list. For each string in the list, the split_string_on_char function is called once.
Therefore, the overall time complexity of the split_list_on_char function is O(n^2).
Space complexity:

The space complexity of the split_string_on_char function is O(n), where n is the length of the string (due to the recursive calls).
The space complexity of the reduce function in the split_list_on_char function is O(n), where n is the length of the input list (due to the result list).
Therefore, the overall space complexity of the split_list_on_char function is O(n^2).