2788. Split Strings by Separator

EasyArrayString

Problem Description

In this problem, we have an input array words which consists of strings, and a separator, which is a single character. Our task is to take each string in words and split it into substrings based on where the separator occurs. Once we split the strings, we need to exclude any empty substrings that may result from this process. The output should be a new array of strings which represents the initial strings split by the separator, maintaining the original order of the strings in words. Importantly, the separator itself should not be included in the resulting strings.

Intuition

The intuition behind the solution is to use the built-in string function split() which is available in Python. The split() function takes a character or substring and splits the string at every occurrence of this character or substring. This works perfectly for our use case with the separator. The idea is to iterate through each string in the words array, apply the split(separator) function to divide it into substrings, and collect the resulting substrings in the new output array. However, because we should not include any empty strings in the output, we add a condition to only include substrings that are not empty (if s).

This approach allows us to construct the desired output array with each string being split by the separator and empty strings being excluded, all while keeping the order of the originally provided strings intact.

Solution Approach

The solution leverages the power of list comprehension in Python, which is a compact way to process elements in a list and construct a new list based on certain criteria. There are three main parts to our list comprehension:

Iterating over each word in the input words list.
Splitting each word by the given separator to create a list of substrings.
Filtering out any resulting empty strings.

These steps can be broken down as follows:

Iteration: The outer loop for w in words goes through each string w present in the input list words.
Split Operation: For each string w, w.split(separator) is called. This function returns a list of substrings obtained by splitting w at every occurrence of the character separator.
Filtering Empty Strings: Inside the list comprehension, after the split operation, there's another loop for s in w.split(separator). Here, s represents each substring result from the split. The if s part ensures that only non-empty s (substrings) get included in the final list. This filtering is important to meet the problem's requirement to exclude empty strings.
Creating the Output List: The list comprehension [s for w in words for s in w.split(separator) if s] then constructs the output list. This list includes all non-empty substrings obtained from splitting each of the strings in words by the separator.

Code Analysis: The given solution code uses no additional data structures other than the list to hold the final result. It's a direct application of string manipulation methods and list comprehension, which are very efficient for this kind of task. The overall time complexity is O(n * m), where n is the number of strings in the input list and m is the average length of the strings, assuming split() is O(m) in time.

In conclusion, this implementation is a straightforward and effective way of achieving the desired functionality using Python's string manipulation capabilities and list comprehension.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the provided solution approach with a small example to better understand how it works. Suppose we have the following inputs:

words: ["apple,berry,cherry", "lemon##lime", "banana--melon"]
separator: "-"

We want our output to exclude the separator and not to include any empty strings that may come from split operation. Here's how the solution approach applies to our example:

Step 1: Iterating over each word We start by taking the first string in the words list which is "apple,berry,cherry". Since our separator is "-", this string does not get split as it does not contain the separator.

Step 2: Splitting each word We then move to the second string "lemon##lime". Again, this does not contain our separator, so it remains unsplit.

Step 3: Filtering out empty strings Next, we take the third string "banana--melon". Using the split('-') function on this string gives us ["banana", "", "melon"]. We find that there is an empty string present as a result of the split operation where two separators were adjacent.

Step 4: Applying the list comprehension As per the list comprehension [s for w in words for s in w.split(separator) if s], we construct a new list by including each non-empty substring. For our example, the list comprehension step would look like this:

result = [s for w in ["apple,berry,cherry", "lemon##lime", "banana--melon"] for s in w.split("-") if s]

This will iterate over each word, split it by the separator, and only include the non-empty substrings. In this case, the first two words won't get split because they do not contain the separator. In the third word, "banana--melon", it will split into ["banana", "", "melon"] and exclude the empty string.

The final output array after applying the list comprehension to our example would therefore be:

["apple,berry,cherry", "lemon##lime", "banana", "melon"]

Conclusion: The initial strings are split wherever the separator is encountered, and any strings that would have been empty after the split are removed from the output. The order of the elements is preserved from the original list to the output list.

Solution Implementation

1from typing import List
2
3class Solution:
4    def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
5        # Initialize an empty list to store the split words
6        split_words = []
7      
8        # Iterate through each word in the input list 'words'
9        for word in words:
10            # Split the word by the given separator
11            word_parts = word.split(separator)
12            # Append each non-empty part of the split word to 'split_words'
13            for part in word_parts:
14                if part:  # Ensure to add only non-empty strings
15                    split_words.append(part)
16      
17        # Return the list containing all split, non-empty words
18        return split_words
19

1import java.util.regex.Pattern; // Importing the Pattern class for regex operations.
2import java.util.ArrayList; // Importing the ArrayList class for dynamic array operations.
3import java.util.List; // Importing the List interface for using lists.
4
5// Class name should be capitalized and descriptive
6class WordSplitter {
7
8    // Method to split strings in a list by a given separator and return a list of substrings
9    public List<String> splitWordsBySeparator(List<String> words, char separator) {
10        // Creating a list to store the resulting substrings
11        List<String> splitWords = new ArrayList<>();
12      
13        // Iterating through each string in the list of words
14        for (String word : words) {
15            // Splitting the current word by the separator and escaping it if it's a special regex character
16            String[] parts = word.split(Pattern.quote(String.valueOf(separator)));
17          
18            // Adding each non-empty part to the result list
19            for (String part : parts) {
20                if (!part.isEmpty()) {
21                    splitWords.add(part);
22                }
23            }
24        }
25      
26        // Returning the list of split substrings
27        return splitWords;
28    }
29}
30

1#include <vector>
2#include <string>
3#include <sstream>
4
5class Solution {
6public:
7    // Splits words in the vector by a specified separator and
8    // returns a vector of the subsequently separated strings.
9    // Empty strings resulting from the split are not included in the results.
10    std::vector<std::string> splitWordsBySeparator(std::vector<std::string>& words, char separator) {
11        std::vector<std::string> results;
12      
13        // Iterate over each word in the input vector
14        for (auto& word : words) {
15            // Split the word by the provided separator
16            std::vector<std::string> splitParts = split(word, separator);
17          
18            // Add non-empty parts to the result vector
19            for (auto& part : splitParts) {
20                if (!part.empty()) {
21                    results.emplace_back(part);
22                }
23            }
24        }
25      
26        return results;
27    }
28
29    // Splits a string by a given delimiter and returns a vector of the parts.
30    std::vector<std::string> split(std::string& inputString, char delimiter) {
31        std::vector<std::string> parts;
32        std::stringstream stream(inputString);
33        std::string segment;
34      
35        // Use getline to split the string by the delimiter and add each part to the vector
36        while (getline(stream, segment, delimiter)) {
37            parts.push_back(segment);
38        }
39      
40        return parts;
41    }
42};
43

1// This function takes an array of strings and a separator, then splits each
2// string in the array by the separator, and returns a new array with the split segments.
3// Empty strings resulted from the split are excluded from the result.
4// 
5// @param words - An array of strings to be split.
6// @param separator - A string representing the separator to be used for splitting the words.
7// @returns An array of strings containing the non-empty segments after splitting.
8function splitWordsBySeparator(words: string[], separator: string): string[] {
9    // Initialize an array to store the result segments.
10    const splitWords: string[] = [];
11
12    // Loop through each word in the input array.
13    for (const word of words) {
14        // Split the current word by the given separator.
15        const splits = word.split(separator);
16
17        // Loop through the split segments of the current word.
18        for (const split of splits) {
19            // Add the non-empty segments to the result array.
20            if (split.length > 0) {
21                splitWords.push(split);
22            }
23        }
24    }
25
26    // Return the result array containing all non-empty segments.
27    return splitWords;
28}
29

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by the number of operations it needs to perform in relation to the input size. Here, we consider both the number of words n and the average length of the words m.

The function consists of a list comprehension with a nested loop - for every word w in words, it performs a .split(separator) operation. The .split(separator) operation is O(m) where m is the length of the word being split. This is because .split() goes through each character in the word w to check if it matches the separator.

After splitting, the words are iterated over again to filter out empty strings. This operation can potentially include each character from the previous step, which keeps the complexity at the same level - O(m * n).

Therefore, the overall time complexity is O(m * n), where n is the number of words and m is the average length of those words.

Space Complexity

The space complexity of the function depends on the space required to store the output list.

In the worst case, if the separator is not present in any of the words, then the list comprehension will include all the original words. In this case, the space complexity is equal to the total number of characters in all words (plus the space required for list overhead), which is O(m * n).

However, if the separator is present, then additional strings will be added to the output for each split occurrence. In the absolute worst case, if every character is a separator, the size of the output list could be up to twice the number of characters (since you get an empty string before and after each character), which leads to a space complexity of O(2 * m * n). Since constant factors are dropped in Big O notation, this also simplifies to O(m * n).

So, the space complexity is also O(m * n) under the assumption that the separator can be arbitrarily often in the words.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: