Problem

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.

A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.

  • For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Examples

Example 1

1
2
3

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Example 2

1
2
3

Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.

Constraints

  • 2 <= s.length <= 200
  • s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
  • The number of words in s is between 1 and 9.
  • The words in s are separated by a single space.
  • s contains no leading or trailing spaces.

Solution

Method 1 - Array Placement

Intuition

Since each word has a number (1-9) indicating its position, we can directly place each word in the correct position in an array and then join them.

Approach

  1. Split the input string into words
  2. Create an array of size equal to number of words
  3. For each word, extract the last character (position number) and place the word (without the number) at that position
  4. Join the words to form the final sentence

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <string>
#include <vector>
#include <sstream>
using namespace std;

string sortSentence(string s) {
    istringstream iss(s);
    string word;
    vector<string> words;
    
    while (iss >> word) {
        words.push_back(word);
    }
    
    vector<string> result(words.size());
    
    for (const string& w : words) {
        int pos = w.back() - '1'; // Convert to 0-indexed
        result[pos] = w.substr(0, w.length() - 1); // Remove the number
    }
    
    string answer = "";
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) answer += " ";
        answer += result[i];
    }
    
    return answer;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import (
    "strconv"
    "strings"
)

func sortSentence(s string) string {
    words := strings.Split(s, " ")
    result := make([]string, len(words))
    
    for _, word := range words {
        pos, _ := strconv.Atoi(string(word[len(word)-1]))
        result[pos-1] = word[:len(word)-1] // Remove the number, convert to 0-indexed
    }
    
    return strings.Join(result, " ")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public String sortSentence(String s) {
        String[] words = s.split(" ");
        String[] result = new String[words.length];
        
        for (String word : words) {
            int pos = word.charAt(word.length() - 1) - '1'; // Convert to 0-indexed
            result[pos] = word.substring(0, word.length() - 1); // Remove the number
        }
        
        return String.join(" ", result);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun sortSentence(s: String): String {
        val words = s.split(" ")
        val result = Array(words.size) { "" }
        
        for (word in words) {
            val pos = word.last().digitToInt() - 1 // Convert to 0-indexed
            result[pos] = word.dropLast(1) // Remove the number
        }
        
        return result.joinToString(" ")
    }
}
1
2
3
4
5
6
7
8
9

def sortSentence(s: str) -> str:
    words = s.split()
    result = [''] * len(words)
    
    for word in words:
        pos = int(word[-1]) - 1  # Convert to 0-indexed
        result[pos] = word[:-1]  # Remove the number
    
    return ' '.join(result)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

pub fn sort_sentence(s: String) -> String {
    let words: Vec<&str> = s.split_whitespace().collect();
    let mut result = vec![String::new(); words.len()];
    
    for word in words {
        let pos = word.chars().last().unwrap().to_digit(10).unwrap() as usize - 1;
        result[pos] = word[..word.len()-1].to_string();
    }
    
    result.join(" ")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function sortSentence(s: string): string {
    const words = s.split(' ');
    const result: string[] = new Array(words.length);
    
    for (const word of words) {
        const pos = parseInt(word[word.length - 1]) - 1; // Convert to 0-indexed
        result[pos] = word.slice(0, -1); // Remove the number
    }
    
    return result.join(' ');
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the input string (single pass through words)
  • 🧺 Space complexity: O(n) for storing the words and result array