Python – Extract String elements from Mixed Matrix

Given a Matrix, Extract all the elements that are of string data type.

Input : test_list = [[5, 6, 3], ["Gfg", 3], [9, "best", 4]] 
Output : ['Gfg', 'best'] 
Explanation : All strings are extracted.

Input : test_list = [["Gfg", 3], [9, "best", 4]] 
Output : ['Gfg', 'best'] 
Explanation : All strings are extracted. 

Method #1 : Using list comprehension + isinstance()

The combination of above functions can be used to solve this problem. In this, we iterate nested lists using list comprehension and check for string instance using isinstance().

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'is', 'best']

Time Complexity: O(n) where n is the number of elements in the list “test_list”. 
Auxiliary Space: O(1) additional space is not needed.

Method #2 :  Using chain.from_iterables() + list comprehension + isinstance()

This is yet another way in which this task can be performed. Whole Matrix is flattened and then isinstance() is applied over it to check for string elements in flattened list.

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'is', 'best']

Method #3 : Using extend() and type() methods

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'is', 'best']

Method #4: Using nested loops

1. Initialize an empty list res.
2. Loop through each sublist in test_list.
3. For each sublist, loop through each element.
4. Check if the element is a string using isinstance() function.
5. If the element is a string, append it to the res list.
6. Finally, print the res list.

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'is', 'best']

Time complexity: O(n^2) where n is the length of test_list. 
Auxiliary space: O(m) where m is the number of string elements in the list.

Method #5 : Using reduce():

Algorithm :

1. Initialize a 2D list named test_list containing three sublists, each with a mix of integer and string elements.
2. Print the original list.
3. Initialize an empty list named res to store the string elements.
4. Iterate over each sublist in test_list.
5. For each sublist, iterate over each element.
6. If the element is a string, append it to the res list.
7. After all elements have been checked, return the res list containing all string elements.
8. Print the resulting list of string elements.
    

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'is', 'best']

The time complexity : O(n*m) where n is the number of sublists in test_list and m is the length of the longest sublist. This is because we are iterating over each element of each sublist using the nested for loops, and the isinstance() function has a constant time complexity.

The space complexity : O(m) because we are creating a new list to store the resulting string elements, and the size of this list is proportional to the number of string elements in the matrix.

Method #6 : Using  heapq:

Algorithm :

1. Initialize an empty list res to store the string elements.
2. Use a list comprehension to iterate over each sublist in the input list.
3. Filter the string elements from each sublist using filter() and a lambda function that checks if an element is an instance of a string.
4. Merge the filtered sublists using heapq.merge() to create an iterator that yields the string elements in ascending order.
5. Convert the iterator to a list using list().
6. Store the resulting list of string elements in the res list.
7. Return the res list.

The original list : [[5, 6, 3], ['Gfg', 3, 'is'], [9, 'best', 4]]
The String instances : ['Gfg', 'best', 'is']

Time Complexity:

The time complexity of this algorithm is O(NlogN), where N is the total number of elements in the input list. This is because the heapq.merge() method uses a heap data structure that requires O(logN) time to insert and extract elements, and it is performed on each sublist.
Space Complexity:

The space complexity of this algorithm is O(N), where N is the total number of elements in the input list. This is because the filter() method creates a new list of filtered elements for each sublist in the input list, and the resulting list of string elements is stored in the res list.