Split Strings by Separator
EasyPrompt
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
separatoris 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 <= 1001 <= words[i].length <= 20- characters in
words[i]are either lowercase English letters or characters from the string".,|$#@"(excluding the quotes) separatoris a character from the string".,|$#@"(excluding the quotes)
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages the built-in split() method available for strings in most programming languages. It's a straightforward and concise way to solve the problem.
Algorithm
- Initialize an empty list,
result, to store the final split strings. - Create a regex-safe string from the
separatorcharacter, for example, by usingPattern.quote(). - Iterate through each
wordin the inputwordslist. - For each
word, call thesplit()method with the quoted separator to get an array of substrings. - Iterate through this array of substrings.
- If a substring is not empty, add it to the
resultlist. - After processing all words, return the
resultlist.
Walkthrough
The core idea is to iterate through each word in the input list and use the String.split() method to break it into parts based on the given separator. The split method in Java uses regular expressions, so it's important to treat the separator character as a literal string to avoid unintended behavior with special regex characters like ., |, or $. This can be achieved using Pattern.quote(). After splitting, we iterate through the resulting parts and add any non-empty strings to our final result list.
import java.util.ArrayList;import java.util.List;import java.util.regex.Pattern; class Solution { public List<String> splitWordsBySeparator(List<String> words, char separator) { List<String> result = new ArrayList<>(); // The separator character might be a special regex metacharacter (e.g., '.', '$', '|'). // Pattern.quote() treats the separator as a literal character for the split operation. String regexSeparator = Pattern.quote(String.valueOf(separator)); for (String word : words) { String[] parts = word.split(regexSeparator); for (String part : parts) { if (!part.isEmpty()) { result.add(part); } } } return result; }}Complexity
Time
O(K), where K is the total number of characters across all words. The `split` operation needs to scan the entire string, and we iterate through all words.
Space
O(K), where K is the total number of characters across all words. This space is used to store the resulting list of strings. Additionally, the `split` method creates temporary intermediate arrays, which also contribute to the space usage.
Trade-offs
Pros
Very concise and easy to read and write.
Leverages the standard library, which is generally well-tested and reliable.
Cons
Can be less performant due to the overhead associated with regular expression compilation and matching, even for a simple character separator.
Creates intermediate arrays for each word's split parts, which can lead to slightly higher memory consumption and garbage collection pressure.
This approach manually iterates through each character of every word to identify the separator and build the substrings. It avoids the overhead of regular expressions, often leading to better performance.
Algorithm
- Initialize an empty list,
result. - Iterate through each
wordin the inputwordslist. - Inside the loop, initialize an empty
StringBuildercalledcurrentPart. - Iterate through each character
cof the currentword. - If
cis theseparator:- If
currentPartis not empty, add its string representation toresult. - Reset
currentPart.
- If
- Else (if
cis not theseparator):- Append
ctocurrentPart.
- Append
- After iterating through all characters of a
word, check ifcurrentPartis not empty. If so, add its content toresult. This handles the case where a word does not end with a separator. - Return the
resultlist.
Walkthrough
We iterate through each word from the input list. For each word, we iterate through its characters one by one. We use a StringBuilder to construct the current part of the string. When we encounter a character that is not the separator, we append it to the StringBuilder. If we encounter the separator, it marks the end of a potential part. We then check if the StringBuilder has accumulated any characters. If it has, we convert it to a string, add it to our result list, and reset the StringBuilder for the next part. After the inner loop finishes for a word, we must perform one final check to add the last part if the word doesn't end with a separator.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> splitWordsBySeparator(List<String> words, char separator) { List<String> result = new ArrayList<>(); for (String word : words) { StringBuilder currentPart = new StringBuilder(); for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (c == separator) { if (currentPart.length() > 0) { result.add(currentPart.toString()); currentPart.setLength(0); // Reset for the next part } } else { currentPart.append(c); } } // Add the last part if the word doesn't end with a separator if (currentPart.length() > 0) { result.add(currentPart.toString()); } } return result; }}Complexity
Time
O(K), where K is the total number of characters. We visit each character exactly once.
Space
O(K), where K is the total number of characters. This space is required for the output list. The `StringBuilder` uses O(M) auxiliary space, where M is the maximum word length.
Trade-offs
Pros
More performant than the regex-based approach as it avoids the overhead of regex engines.
Generally more memory-efficient as it doesn't create intermediate arrays of strings for each split operation.
Cons
The code is more verbose and less concise than using a built-in
splitfunction.Requires careful implementation to handle all edge cases correctly, such as the last substring in a word.
Solutions
Solution
import java.util.regex.Pattern ; class Solution { public List < String > splitWordsBySeparator ( List < String > words , char separator ) { List < String > ans = new ArrayList <>(); for ( var w : words ) { for ( var s : w . split ( Pattern . quote ( String . valueOf ( separator )))) { if ( s . length () > 0 ) { ans . add ( s ); } } } return ans ; } }class Solution {public: vector<string> splitWordsBySeparator(vector<string> &words, char separator) { vector<string> ans; for (const auto &w : words) { istringstream ss(w); string s; while (getline(ss, s, separator)) { if (!s.empty()) { ans.push_back(s); } } } return ans; }};class Solution: def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]: return [ s for w in words for s in w . split(separator) if s]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.