Split Strings by Separator

Easy

Asked by:

35 views

Topics:

ArraysStrings

Given an array of strings words and a character separator, split each string in words by separator.

Return an array of strings containing the new strings formed after the splits, excluding empty strings.

Notes

separator is used to determine where the split should occur, but it is not included as part of the resulting strings.
A split may result in more than two strings.
The resulting strings must maintain the same order as they were initially given.

Example 1:

Input: words = ["one.two.three","four.five","six"], separator = "."
Output: ["one","two","three","four","five","six"]
Explanation: In this example we split as follows:

"one.two.three" splits into "one", "two", "three"
"four.five" splits into "four", "five"
"six" splits into "six" 

Hence, the resulting array is ["one","two","three","four","five","six"].

Example 2:

Input: words = ["$easy$","$problem$"], separator = "$"
Output: ["easy","problem"]
Explanation: In this example we split as follows: 

"$easy$" splits into "easy" (excluding empty strings)
"$problem$" splits into "problem" (excluding empty strings)

Hence, the resulting array is ["easy","problem"].

Example 3:

Input: words = ["|||"], separator = "|"
Output: []
Explanation: In this example the resulting split of "|||" will contain only empty strings, so we return an empty array [].

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
characters in words[i] are either lowercase English letters or characters from the string ".,|$#@" (excluding the quotes)
separator is a character from the string ".,|$#@" (excluding the quotes)

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings and the separator contain Unicode characters or are they limited to ASCII?
What should I return if any of the strings in the input array are empty?
Is the separator guaranteed to be a single character, or can it be a string of multiple characters?
If a string in the input array consists only of the separator character, should an empty string be included in the result for that input string?
Are leading or trailing separator characters in a string significant, or should I trim them before splitting?

Brute Force Solution

Approach

The brute force approach to splitting strings involves examining every possible combination of splits. We essentially try out every conceivable way to divide the strings and then select the correct answer. It's like trying every possibility until we find the right one.

Here's how the algorithm would work step-by-step:

Consider each string one at a time.
For each string, check every position to see if it's the separator we're looking for.
If we find the separator, we cut the string at that position.
Add the parts of the string we found between separators to a list.
Once we've looked at every position in every string, we will have a complete list of all the pieces.

Code Implementation

def split_strings_by_separator_brute_force(strings, separator):
    result_list = []
    for input_string in strings:
        current_string = ""
        for character in input_string:
            # Check if the current character is the separator
            if character == separator:

                if current_string:
                    result_list.append(current_string)

                # Reset the current string
                current_string = ""
            else:
                current_string += character

        # Add the last part if it's not empty.
        if current_string:
            result_list.append(current_string)

    return result_list

Big(O) Analysis

Time Complexity

O(N*M) – Let N be the number of strings in the input list, and let M be the maximum length of any string in the input list. For each of the N strings, we iterate through each of its characters, which takes at most M steps. Therefore, the total number of operations is proportional to N*M, resulting in a time complexity of O(N*M).

Space Complexity

O(M) – The primary contributor to auxiliary space is the list used to store the resulting string parts. In the worst-case scenario, where each character in the input strings (across all input strings) is a substring between separators, this list will contain a number of string parts proportional to the total number of characters in all the input strings, where M is the total number of characters across all input strings. The space used to store each string part depends on the length of the string part which can at most be the length of original strings. Other variables used such as indices are constant space.

Optimal Solution

Approach

The most efficient way to split strings is to use the built-in string processing tools available in the programming language. This avoids writing complicated logic and makes the code simpler and faster. The approach involves checking each string and extracting parts based on a designated separator.

Here's how the algorithm would work step-by-step:

For each string in the input, use the built-in function that finds all occurrences of the separator.
Use the location of each separator to extract all the substrings located between the separators.
If there are multiple separators one after the other, this will create empty substrings, so remove them from the list of substrings.
Put all of the split strings into a single big list of results to return at the end.

Code Implementation

def split_strings_by_separator(strings, separator):
    result = []
    for string in strings:
        # Use the string's built-in split function.
        split_strings = string.split(separator)

        substrings = []
        for split_string in split_strings:
            # Avoid adding empty strings caused by consecutive separators.
            if split_string:
                substrings.append(split_string)

        # Add substrings to the overall result.
        result.extend(substrings)

    return result

Big(O) Analysis

Time Complexity

O(N*M) – Let N be the number of strings in the input array and M be the maximum length of any single string. Iterating through the N strings contributes a factor of N. Within each string, finding the separator and extracting substrings takes time proportional to the string's length, up to a maximum of M. Therefore, the overall time complexity is proportional to N*M, where N is the number of strings and M is the maximum length of the string, representing the worst-case scenario of scanning each string.

Space Complexity

O(N) – The space complexity is dominated by the single big list used to store all the split strings. In the worst-case scenario, if the separator is rare or absent, each input string of length up to N could contribute a significant portion (or all) of its characters to the result list. Therefore, the size of this list can grow linearly with the total number of characters across all input strings, where N represents the combined length of all input strings. Other temporary variables have constant space requirements compared to the result list.

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty list if the input string is null or empty to avoid null pointer exceptions or unexpected behavior.
Null separator	Throw IllegalArgumentException as a null separator is not meaningful.
Empty separator	Split the string into an array of single characters.
Separator not found in the string	Return a list containing the original string as the only element since there is nothing to split.
String consists only of the separator	Return an empty list because there are no substrings between the separators.
String starts and ends with the separator	Ensure empty strings are included in the result list for the beginning and end of the string.
Consecutive separators in the string	Ensure empty strings are added to the result list for each instance of consecutive separators.
Very long string or very long separator	The solution should be memory efficient and avoid excessive string copying or intermediate data structures that could lead to out-of-memory errors for extremely large strings.

Null or empty string input

How to Handle:

Return an empty list if the input string is null or empty to avoid null pointer exceptions or unexpected behavior.

Null separator

How to Handle:

Throw IllegalArgumentException as a null separator is not meaningful.

Empty separator

How to Handle:

Split the string into an array of single characters.

Separator not found in the string

How to Handle:

Return a list containing the original string as the only element since there is nothing to split.

String consists only of the separator

How to Handle:

Return an empty list because there are no substrings between the separators.

String starts and ends with the separator

How to Handle:

Ensure empty strings are included in the result list for the beginning and end of the string.

Consecutive separators in the string

How to Handle:

Ensure empty strings are added to the result list for each instance of consecutive separators.

Very long string or very long separator

How to Handle:

The solution should be memory efficient and avoid excessive string copying or intermediate data structures that could lead to out-of-memory errors for extremely large strings.