algoadvance

The problem requires writing a function sortSentence that takes a single string s as input. The string represents a jumbled sentence where each word is appended with a digit indicating its position in the original sentence. Your task is to reconstruct and return the sentence in its original order, removing the digits.

Example:

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"

Clarifying Questions

1. Q: Can there be multiple spaces between words?
   A: No, you can assume there is a single space between words.

2. Q: Will the input sentence always be valid and contain all words correctly suffixed by digits?
   A: Yes, you can assume the input is always valid.

3. Q: What is the range of the input length?
   A: The input length s is within the range of 1 to 200.

Code

def sortSentence(s: str) -> str:
    # Split the input string into words
    words = s.split()
    
    # Create a list for sorted words placed in their correct positions
    sorted_words = [""] * len(words)
    
    # Iterate through each word to strip the number and place it in its position
    for word in words:
        index = int(word[-1]) - 1  # Get the position and convert to zero-indexed
        sorted_words[index] = word[:-1]  # Remove the digit and place the word
    
    # Join the sorted words to form the final sentence
    return " ".join(sorted_words)

# Example usage
s = "is2 sentence4 This1 a3"
print(sortSentence(s))  # Output: "This is a sentence"

Strategy

1. Splitting the Sentence:
   Split the input string s by spaces to get individual word fragments. Each fragment will contain a word followed by a digit.

2. Creating Sorted List: Initialize a list sorted_words to store the sorted words according to their positions indicated by the digits.

3. Placing Words Correctly: Iterate through each fragment, extract the digit and convert it to a zero-index position. Remove the digit from the word and place it in the sorted_words list at the correct index.

4. Forming the Final Sentence: Join all elements of the sorted_words list into a single string with spaces to form the correctly ordered sentence.

Time Complexity

• Splitting the input string:
  This operation takes O(n) where n is the length of the string, since Python’s split function is linear.

• Iterating and placing words:
  The iteration through the list and placing words in the correct index also takes O(n), since each word is processed once.

Thus, the overall time complexity is O(n), where n is the number of characters in the input string s.

Try our interview co-pilot at AlgoAdvance.com

• 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?