2788. Split Strings by Separator
Problem Description
You are given an array of strings called words
and a character called separator
. Your task is to split each string in the words
array using the separator
character as a delimiter.
The problem asks you to:
- Go through each string in the
words
array - Split each string wherever the
separator
character appears - Collect all the resulting substring pieces into a new array
- Remove any empty strings from the result
- Maintain the original order of the strings
Important details:
- The
separator
character itself should not be included in the resulting strings - it only marks where to split - When a string is split, it might produce more than two parts (if the separator appears multiple times)
- Empty strings that result from the splitting process should be excluded from the final answer
- The order of strings in the result should follow the order they appeared in the original array
For example, if words = ["hello.world", "test..case"]
and separator = "."
, the splitting process would:
- Split "hello.world" into ["hello", "world"]
- Split "test..case" into ["test", "", "case"] (but the empty string would be removed)
- Return ["hello", "world", "test", "case"]
The solution uses a list comprehension that iterates through each word w
in words
, splits it by the separator
, and only includes non-empty strings s
in the final result.
Intuition
The problem is essentially asking us to perform a two-step process: split strings and then filter out empty results. When we think about this naturally, we would:
- Take each word one by one
- Split it based on the separator
- Collect all the pieces
- Remove any empty pieces
Python's built-in split()
method already handles the splitting part perfectly - it breaks a string into parts wherever it finds the separator. The key insight is that we need to process multiple words and combine all their split results into a single flat list.
Instead of using nested loops explicitly, we can leverage Python's list comprehension to elegantly express this pattern. The nested comprehension [s for w in words for s in w.split(separator)]
naturally flattens the results - it's like saying "for each word, split it, and for each piece from that split, add it to our result."
The filtering part comes from recognizing that when we split strings like "a..b" with separator ".", we get ['a', '', 'b']
- those empty strings need to be removed. Adding the condition if s
at the end of the comprehension elegantly filters these out, since empty strings evaluate to False
in Python.
This approach is intuitive because it mirrors exactly how we'd manually solve this problem: go through each word, break it apart at the separator, keep the non-empty pieces, and collect everything in order. The list comprehension just expresses this process concisely in a single line.
Solution Approach
The solution uses a simulation approach where we traverse through each string in the array and perform the split operation. Here's how the implementation works:
We iterate through the string array words
and for each string w
, we apply the split(separator)
method. This built-in method divides the string into substrings wherever the separator
character appears.
The implementation uses a nested list comprehension with three key components:
- Outer iteration:
for w in words
- This iterates through each string in the input array - Inner iteration:
for s in w.split(separator)
- For each wordw
, we split it using the separator and iterate through the resulting substrings - Filtering condition:
if s
- This ensures we only include non-empty strings in our result
The complete list comprehension [s for w in words for s in w.split(separator) if s]
effectively flattens and filters the results in a single pass.
Let's trace through an example:
- If
words = ["one.two.three", "four..five"]
andseparator = "."
- For "one.two.three":
split(".")
gives["one", "two", "three"]
- For "four..five":
split(".")
gives["four", "", "five"]
- The
if s
condition filters out the empty string - Final result:
["one", "two", "three", "four", "five"]
The time complexity is O(n × m) where n is the total number of characters across all strings and m is the average number of separators per string. The space complexity is O(n) for storing the result array.
This approach maintains the required order naturally since we process the words sequentially and append the split results in the order they appear.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example to see how the solution works step by step.
Input: words = ["abc.def", "ghi..jkl", "m"]
, separator = "."
Step 1: Process the first word "abc.def"
- Apply
split(".")
→["abc", "def"]
- Both strings are non-empty, so both are included
- Current result:
["abc", "def"]
Step 2: Process the second word "ghi..jkl"
- Apply
split(".")
→["ghi", "", "jkl"]
- We get an empty string in the middle because there are two consecutive dots
- Filter with
if s
condition:- "ghi" is non-empty → include it
- "" is empty → skip it
- "jkl" is non-empty → include it
- Current result:
["abc", "def", "ghi", "jkl"]
Step 3: Process the third word "m"
- Apply
split(".")
→["m"]
- No separator found, so the whole string becomes one element
- "m" is non-empty → include it
- Final result:
["abc", "def", "ghi", "jkl", "m"]
The list comprehension [s for w in words for s in w.split(separator) if s]
handles all these steps in one expression:
- The outer loop (
for w in words
) goes through each word - The inner loop (
for s in w.split(separator)
) processes each split piece - The condition (
if s
) ensures only non-empty strings make it to the final result
This maintains the original order and correctly handles edge cases like consecutive separators or strings without any separators.
Solution Implementation
1from typing import List
2
3class Solution:
4 def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
5 """
6 Split each word in the list by the given separator and return all non-empty substrings.
7
8 Args:
9 words: A list of strings to be split
10 separator: The character used to split each word
11
12 Returns:
13 A list containing all non-empty substrings after splitting
14 """
15 # Initialize result list to store all non-empty substrings
16 result = []
17
18 # Iterate through each word in the input list
19 for word in words:
20 # Split the current word by the separator
21 split_parts = word.split(separator)
22
23 # Add only non-empty parts to the result
24 for part in split_parts:
25 if part: # Check if the part is not empty
26 result.append(part)
27
28 return result
29
1import java.util.List;
2import java.util.ArrayList;
3import java.util.regex.Pattern;
4
5class Solution {
6 public List<String> splitWordsBySeparator(List<String> words, char separator) {
7 // Initialize result list to store split words
8 List<String> result = new ArrayList<>();
9
10 // Iterate through each word in the input list
11 for (String word : words) {
12 // Split the current word by the separator character
13 // Pattern.quote() escapes special regex characters to treat them literally
14 String[] splitParts = word.split(Pattern.quote(String.valueOf(separator)));
15
16 // Add non-empty parts to the result list
17 for (String part : splitParts) {
18 if (part.length() > 0) {
19 result.add(part);
20 }
21 }
22 }
23
24 // Return the list of all split words
25 return result;
26 }
27}
28
1class Solution {
2public:
3 vector<string> splitWordsBySeparator(vector<string>& words, char separator) {
4 vector<string> result;
5
6 // Iterate through each word in the input vector
7 for (const auto& word : words) {
8 // Create a string stream from the current word
9 istringstream stringStream(word);
10 string segment;
11
12 // Split the word by the separator using getline
13 while (getline(stringStream, segment, separator)) {
14 // Only add non-empty segments to the result
15 if (!segment.empty()) {
16 result.push_back(segment);
17 }
18 }
19 }
20
21 return result;
22 }
23};
24
1/**
2 * Splits words in an array by a separator character and returns non-empty results
3 * @param words - Array of strings to be split
4 * @param separator - Character used as the delimiter for splitting
5 * @returns Array of non-empty strings after splitting
6 */
7function splitWordsBySeparator(words: string[], separator: string): string[] {
8 // Use flatMap to split each word and flatten the result into a single array
9 // Filter out empty strings that may result from consecutive separators or leading/trailing separators
10 return words.flatMap((word: string) =>
11 word.split(separator).filter((segment: string) => segment.length > 0)
12 );
13}
14
Time and Space Complexity
Time Complexity: O(n × m)
The algorithm iterates through each word in the words
list (n words total). For each word, it performs a split()
operation which takes O(m)
time where m is the length of the current word (in worst case, the maximum length among all words). The split operation needs to scan through the entire string to find all occurrences of the separator. Therefore, the overall time complexity is O(n × m)
where n is the number of words and m is the maximum length of strings in the array.
Space Complexity: O(m)
The space complexity is determined by the temporary space used during the split operation. When w.split(separator)
is called, it creates a list of substrings from the word w. In the worst case, if a word of maximum length m contains no separators, the split operation creates a list containing the entire word, requiring O(m)
space. Although the final result list might contain multiple split words, the space analysis focuses on the auxiliary space used during computation, not the output space. The list comprehension processes one word at a time, so the maximum auxiliary space needed at any point is O(m)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Confusing Split Behavior with Multiple Consecutive Separators
The Pitfall: Many developers incorrectly assume that consecutive separators will be treated as a single separator. In reality, each separator creates a split point, potentially generating empty strings between consecutive separators.
For example, with word = "a..b"
and separator = "."
:
- The split operation produces
["a", "", "b"]
(not["a", "b"]
) - The empty string in the middle represents the "nothing" between the two dots
Why This Happens: The split()
method treats each occurrence of the separator as a boundary. When two separators appear consecutively, there's technically an empty substring between them.
The Solution: The code correctly handles this by filtering out empty strings with the if part:
condition. This ensures that only non-empty substrings make it to the final result.
2. Assuming Single Character Separator
The Pitfall: While the problem typically uses a single character as a separator, Python's split()
method actually accepts strings of any length. If you accidentally pass a multi-character string as the separator, the behavior changes:
# Intended: separator = "." # Accident: separator = ".." word = "hello..world" word.split("..") # Returns ["hello", "world"] word.split(".") # Returns ["hello", "", "world"]
The Solution: Always verify the separator is exactly what you expect. If the problem guarantees a single character, you could add validation:
def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
# Optional validation
if len(separator) != 1:
raise ValueError("Separator must be a single character")
result = []
for word in words:
split_parts = word.split(separator)
for part in split_parts:
if part:
result.append(part)
return result
3. Edge Cases with Empty Input
The Pitfall: Not considering edge cases like:
- Empty
words
array:[]
- Words containing only separators:
["...", "..."]
- Empty strings in the input:
["", "hello", ""]
Why This Matters: These edge cases can cause unexpected behavior or errors if not handled properly.
The Solution: The current implementation handles these gracefully:
- Empty array returns empty result
- Strings with only separators produce empty splits that get filtered out
- Empty strings in input produce no output (correctly filtered)
Test these edge cases explicitly:
# Edge case testing assert splitWordsBySeparator([], ".") == [] assert splitWordsBySeparator(["..."], ".") == [] assert splitWordsBySeparator(["", "a.b", ""], ".") == ["a", "b"]
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!