algoadvance

Leetcode 1859. Sorting the Sentence

Problem Statement

You are given a shuffled sentence containing a list of words separated by spaces. Each word includes a single-digit integer at the end, which indicates the position the word should have in the sentence after sorting. Your task is to reconstruct and return the original sentence.

For example:

Clarifying Questions

  1. Q: Are the words guaranteed to have unique position integers? A: Yes, each word will have a unique integer at the end.

  2. Q: What is the maximum length of the input string? A: The constraints typically found on LeetCode problems will apply, such as length constraints suitable for typical interview problems.

  3. Q: Are there any constraints on the number of words in the sentence? A: Typically, the number of words will be reasonable enough to handle in an interview setting, but there will be at least one word.

  4. Q: Do the words contain only lowercase letters? A: Yes, apart from the digit at the end, the words will contain lowercase English letters.

Strategy

  1. Split the input string by spaces to separate the words.
  2. Extract the last character of each word, which represents the position.
  3. Remove the digit from the word and store the words in an array at the index corresponding to their extracted positions.
  4. Join the words from the sorted positions to form the final sentence.

Code

Here’s the C++ code to solve the problem:

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

std::string sortSentence(const std::string &s) {
    std::stringstream ss(s);
    std::string word;
    std::vector<std::string> words(9); // Assuming no more than 9 words as single-digit positions are used

    // Split the sentence into words and place them in correct position
    while (ss >> word) {
        int position = word.back() - '1'; // Convert char to int and adjust to 0-based index
        word.pop_back(); // Remove the digit from the word
        words[position] = word;
    }

    // Reconstruct the sorted sentence
    std::string sorted_sentence;
    for (const std::string &w : words) {
        if (!w.empty()) {
            if (!sorted_sentence.empty()) {
                sorted_sentence += " ";
            }
            sorted_sentence += w;
        }
    }

    return sorted_sentence;
}

int main() {
    std::string input = "is2 sentence4 This1 a3";
    std::string output = sortSentence(input);
    std::cout << output << std::endl;
    return 0;
}

Time Complexity

Hence, the overall time complexity is O(n), where n is the length of the input string.

Explanation of the Code

  1. We use a stringstream to break the input sentence into words.
  2. Each word is stored in a correct position based on the last character, which signifies its positional order in the reconstructed sentence.
  3. Words are then joined in order to form the final sentence without the positional digits.

By following the steps outlined, we can efficiently translate the shuffled sentence back to its intended order.

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