# Solving Leetcode Interviews in Seconds with AI: Sorting the Sentence


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1859" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.   Example 1:  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:  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.  

	# Explanation
	Here's the breakdown of the approach, complexity, and the Python code:

*   **High-Level Approach:**
    *   Split the input string into individual words.
    *   Extract the original position of each word by looking at the trailing digit. Store the words in a list at their correct index.
    *   Join the sorted words to form the original sentence.

*   **Complexity:**
    *   Runtime Complexity: O(n), where n is the number of words in the sentence.
    *   Storage Complexity: O(n), to store the words in their original order.

	
	# Code
	```python
	def sort_sentence(s: str) -> str:
    """
    Reconstructs the original sentence from a shuffled sentence.

    Args:
        s: The shuffled sentence.

    Returns:
        The original sentence.
    """

    words = s.split()
    n = len(words)
    original_sentence = [""] * n

    for word in words:
        position = int(word[-1]) - 1
        original_sentence[position] = word[:-1]

    return " ".join(original_sentence)
	```