algoadvance

Leetcode 2788. Split Strings by Separator

Problem Statement

Given an array of strings words and a character separator, split each string in words by separator and return all the strings “after splitting” in the same order they appear in. You may return the strings in any order.

Example:

Input: words = ["one.two.three", "four.five", "six"], separator = '.'
Output: ["one", "two", "three", "four", "five", "six"]

Clarifying Questions

1. Q: Are we allowed to use built-in string splitting functions? A: For this problem, you can assume that you need to implement your own function to split the strings.

2. Q: Can the separator character be any character? A: Yes, it can be any character.

3. Q: How should empty segments be treated? A: The behavior for empty segments isn’t clearly stated, but typically we should return such segments unless otherwise specified.

Strategy

1. Initialize Result Vector: Create a vector result to store the substrings after splitting.
2. Iterate Over Input Words: For each string in words:
   • Use a loop to find the delimiter.
   • Extract substrings based on the positions of the delimiter.
   • Add these substrings to the result vector.
3. Return Result: Return the result vector.

Code

Here’s one way to implement this:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> splitStringsBySeparator(vector<string>& words, char separator) {
    vector<string> result;

    // Iterate over each word in the list
    for (const string& word : words) {
        size_t begin = 0;
        size_t end = word.find(separator);

        // Loop to find all separators in the word
        while (end != string::npos) {
            result.push_back(word.substr(begin, end - begin));
            begin = end + 1;
            end = word.find(separator, begin);
        }
        
        // Add the last or the only segment
        result.push_back(word.substr(begin));
    }

    return result;
}

int main() {
    vector<string> words = {"one.two.three", "four.five", "six"};
    char separator = '.';

    vector<string> result = splitStringsBySeparator(words, separator);
    
    cout << "Result: ";
    for (const string& str : result) {
        cout << str << " ";
    }
    cout << endl;
    
    return 0;
}

Time Complexity

• O(N + M) where ( N ) is the total length of all the strings in words and ( M ) is the number of separators.
  • Iterating over each string: O(N) where ( N ) is the total number of characters in all strings combined.
  • Finding and Substring operations: Each find operation and substring operation is O(1) on average since they are linear in the size of the string segment being operated on.

The overall efficiency is effectively linear in terms of the total input size combined with the number of separators. This approach should be optimal for most realistic input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?