Alex Sikorski

Jun 16, 2022

Sorting the Sentence (LeetCode #1859)

The problem starts by dictating what a sentence is:

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.

1. 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:

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

Initial Thoughts

It's clear that we have to look for digits within a loop, since the characters 1 to 9 dictate that a word has been passed in iteration, and whatever characters that come before it, construct a word.

It's also important to realise that the number of words in s range from 1 to 9. This means we can simply use a primitive String[] array with a fixed size of our maximum that is 9, and make use of the default null values that are populated in the array.

Using this array will let us replace values in respective order, where the index is obtained from the detected word, but then we have to think about constructing a String as opposed to returning an array. At glance, this can be easily done with a for loop where we check for not null values and just concatenate for each iteration.

So what happened to the space characters? This would be ignored in our first loop, but appended after each word in our second loop that produces the result. Now, this would produce a trailing space for the last word, but we can simply use the .substring() method to essentially remove that trailing space character.

Solution

class Solution {
    public String sortSentence(String s) {
    
        String[] words = new String[9];
        // constraints mention 1-9 words
        
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            if(Character.isDigit(c)){
                // if character is a digit
                words[Character.getNumericValue(c) - 1] = sb.toString();
                // set array entry at index to string built thus far
                sb.setLength(0);
                // then reset StringBuilder contents
            }
            else if(c != ' ') sb.append(c);
            // else if not an empty space, append to string builder
        }
        
        for(int i = 0; i < 9; i++) if(words[i] != null) sb.append(words[i]).append(' ');
        // last for loop going through 'words' array, if they are not null, append to
        // string builder and always append a space afterwards (will be dealt with later)
        
        return sb.toString().substring(0, sb.toString().length() - 1);
        // substring everything but the last character which would be a space character
    }
}

Result

If this graph is true, this solution would be the most memory optimized result submitted to LeetCode.