1324. Print Words Vertically

MediumArrayStringSimulation
Leetcode Link

Problem Description

The problem presents a situation where we are given a string s which contains a sequence of words separated by spaces. The goal is to return all these words "vertically" in the order they appear in the string. Returning the words vertically means that each word will start at a new column, and the letters from different words at the same column index will be combined into a new string (still preserving the order in which words appear). If the words are of different lengths and we reach a column index where some words have no characters, we use spaces to fill those places. It is also important to note that we should not have any trailing spaces in our final strings.

For example, if s is "HOW ARE YOU", the output should be ["HAY","ORO","WEU"] as each column gives "HAY", "ORO", and "WEU" respectively without the trailing spaces.

Intuition

To solve this problem, we first split the input string into words. Then we need to determine the maximum length among these words because this will tell us how many "vertical" strings we need to form — one for each character position in the longest word.

Next, we iterate over each character position up to the maximum length, and for each position, we build a new vertical word by taking the character from each original word at that position if it exists, or using a space as a placeholder if that word is too short.

While building each vertical word, we should also ensure that we trim trailing spaces. This is crucial so that the resulting vertical words do not end with any unnecessary spaces.

This solution focuses on solving the problem step by step, considering each vertical word as a snapshot of each column in the original words. It's a straightforward approach that uses simple loops and list operations to accomplish the task.

Solution Approach

The implementation of the solution follows a clear and structured algorithmic approach.

  1. Splitting the String: The first step involves splitting the string s into words. This is done using the .split() method in Python, which by default splits a string by spaces, thereby separating individual words into a list.

    1words = s.split()
  2. Determining the Maximum Word Length: Once we have a list of words, we find the length of the longest word using a generator expression inside the max function. This step is crucial as it determines how many vertical strings we need to construct (one for each character of the longest word).

    1n = max(len(w) for w in words)
  3. Creating Vertical Words: The solution then iterates through each character position (using a range of n, the maximum length found). For each position j, we construct a temporary list t, where each element is the j-th character of a word from the original list if that word is long enough; otherwise, it's a space ' '.

    1for j in range(n):
    2    t = [w[j] if j < len(w) else ' ' for w in words]

    This is achieved using a list comprehension that also applies conditional logic - an efficient way to construct lists based on conditional operations in Python.

  4. Trimming Trailing Spaces: After constructing each vertical word, the algorithm trims any trailing spaces from the list t. It does this by checking and popping the last element repeatedly until the last character is not a space.

    1while t[-1] == ' ':
    2    t.pop()
  5. Building the Final Answer: Finally, all the characters in the list t are joined to make a string representing a vertical word, which is then appended to the answer list ans.

    1ans.append(''.join(t))

The algorithm completes when it has created a vertical word for each position in the maximum word length, and the answer list ans is returned containing the correctly formatted vertical representation of the given string. This approach leverages simple data structures, namely lists and strings, combined with straightforward logic for an intuitive solution.

Overall, this solution approach uses common Python data manipulation techniques to transform the input string into the desired vertical orientation step by step. It employs fundamental programming concepts such as loops, list comprehension, conditional statements, and string manipulation to achieve the result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's walk through the solution approach with a small example. Suppose our input string is "TO BE OR NOT TO BE".

  1. Splitting the String: First, we split the input string "TO BE OR NOT TO BE" into individual words.

    1words = "TO BE OR NOT TO BE".split()  # ["TO", "BE", "OR", "NOT", "TO", "BE"]
  2. Determining the Maximum Word Length: We find the longest word's length, which determines the number of vertical strings we need to construct.

    1n = max(len(w) for w in words)  # The longest word is "NOT", so n = 3.
  3. Creating Vertical Words: We iterate over each character position (0 to 2, since the longest word has 3 characters) and build temporary lists for each position, adding spaces if a word is shorter than the current index.

    1# First iteration (j = 0)
    2t = [w[0] if 0 < len(w) else ' ' for w in words]  # ["T", "B", "O", "N", "T", "B"]
    3
    4# Second iteration (j = 1)
    5t = [w[1] if 1 < len(w) else ' ' for w in words]  # ["O", "E", "R", "O", "O", "E"]
    6
    7# Third iteration (j = 2)
    8t = [w[2] if 2 < len(w) else ' ' for w in words]  # [" ", " ", " ", "T", " ", " "]
  4. Trimming Trailing Spaces: We make sure to remove any trailing spaces from our temporary lists after each iteration.

    1# In the third iteration, the list `t` is [" ", " ", " ", "T", " ", " "]
    2while t[-1] == ' ':
    3    t.pop()  # After trimming, `t` becomes [" ", " ", " ", "T"]
  5. Building the Final Answer: Each trimmed list t is then converted to a string and added to our answer list ans.

    1# After the first iteration:
    2ans = ["TBONTB"]
    3
    4# After the second iteration:
    5ans.append(''.join(t))  # ["TBONTB", "ERONTOE"]
    6
    7# After the third iteration:
    8ans.append(''.join(t))  # ["TBONTB", "ERONTOE", "   T"]

After completing these steps for each character position, the answer list ans will look like this: ["TBONTB", "ERONTOE", " T"]. The last step is to make sure no trailing spaces are in the final strings:

1final_ans = [s.rstrip() for s in ans]  # ["TBONTB", "ERONTOE", "T"]

The final output is ["TBONTB", "ERONTOE", "T"]. In this example, each vertical string corresponds to each column of characters from top to bottom, accurately representing the vertical words without trailing spaces as required.

Solution Implementation

1class Solution:
2    def printVertically(self, s: str) -> List[str]:
3        # Split the string into words.
4        words = s.split()
5        # Find the length of the longest word to determine the number of rows.
6        max_length = max(len(word) for word in words)
7      
8        # Create a list to hold the vertical print result.
9        vertical_print = []
10      
11        # Iterate over the range of the maximum length found.
12        for i in range(max_length):
13            # Collect the i-th character of each word if it exists,
14            # otherwise use a space.
15            column_chars = [(word[i] if i < len(word) else ' ') for word in words]
16          
17            # Trim trailing spaces from the right side.
18            while column_chars and column_chars[-1] == ' ':
19                column_chars.pop()
20          
21            # Join the characters to form the vertical word and
22            # append it to the result list.
23            vertical_print.append(''.join(column_chars))
24      
25        # Return the list of vertical words.
26        return vertical_print
27
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5
6    // Function to print words of a string in a vertical order
7    public List<String> printVertically(String s) {
8      
9        // Split the input string into words
10        String[] words = s.split(" ");
11      
12        // The variable 'maxWordLength' will hold the length of the longest word
13        int maxWordLength = 0;
14      
15        // Find the longest word to determine the number of rows in the output
16        for (String word : words) {
17            maxWordLength = Math.max(maxWordLength, word.length());
18        }
19      
20        // Initialize a list to store the resulting vertical strings
21        List<String> result = new ArrayList<>();
22      
23        // Loop through each character index up to the length of the longest word
24        for (int j = 0; j < maxWordLength; ++j) {
25          
26            // Use StringBuilder for efficient string concatenation
27            StringBuilder currentLineBuilder = new StringBuilder();
28          
29            // Loop through each word and append the character at current index,
30            // or append a space if the word is not long enough
31            for (String word : words) {
32                currentLineBuilder.append(j < word.length() ? word.charAt(j) : ' ');
33            }
34          
35            // Remove trailing spaces from the current line
36            while (currentLineBuilder.length() > 0 && 
37                   currentLineBuilder.charAt(currentLineBuilder.length() - 1) == ' ') {
38                currentLineBuilder.deleteCharAt(currentLineBuilder.length() - 1);
39            }
40          
41            // Add the trimmed line to the result list
42            result.add(currentLineBuilder.toString());
43        }
44      
45        // Return the list of vertical strings
46        return result;
47    }
48}
49
1#include <vector>
2#include <string>
3#include <sstream>
4#include <algorithm>
5
6class Solution {
7public:
8    // Function to print words of a string vertically
9    std::vector<std::string> printVertically(std::string s) {
10        // Initialize stringstream for parsing words
11        std::stringstream stream(s);
12      
13        // Container for storing individual words
14        std::vector<std::string> words;
15      
16        // Placeholder for current word extraction
17        std::string word;
18      
19        // Maximum length of words
20        int maxLength = 0;
21        while (stream >> word) { // Extract words one by one
22            words.emplace_back(word); // Add current word to words vector
23            maxLength = std::max(maxLength, static_cast<int>(word.size())); // Update maxLength if current word is longer
24        }
25      
26        // Container for the answer
27        std::vector<std::string> result;
28      
29        // Loop to form words for vertical printing
30        for (int columnIndex = 0; columnIndex < maxLength; ++columnIndex) {
31            std::string verticalWord; // String to hold each vertical word
32
33            // Forming each vertical word by taking character at the current column index
34            for (auto& currentWord : words) {
35                // Add the character if the column index is less than the word length, otherwise, add a space
36                verticalWord += columnIndex < currentWord.size() ? currentWord[columnIndex] : ' ';
37            }
38          
39            // Trim the trailing spaces in the vertical word
40            while (!verticalWord.empty() && verticalWord.back() == ' ') {
41                verticalWord.pop_back(); // Remove the last character if it is a space
42            }
43
44            // Add the trimmed vertical word to the result
45            result.emplace_back(verticalWord);
46        }
47
48        // Return the vector containing the vertically printed words
49        return result;
50    }
51};
52
1// Import statements for TypeScript (if needed)
2// Notably, TypeScript does not have a direct equivalent of C++'s <sstream>, <vector>, or <algorithm>
3// No import is needed here since TypeScript has built-in support for arrays and strings.
4
5// Function to print words of a string vertically
6function printVertically(s: string): string[] {
7    // Split the input string into words based on spaces
8    const words: string[] = s.split(' ');
9
10    // Find the maximum length of the words
11    const maxLength: number = Math.max(...words.map(word => word.length));
12
13    // Initialize an array to hold the results
14    const result: string[] = [];
15
16    // Loop through each column index (0 to maxLength - 1)
17    for (let columnIndex = 0; columnIndex < maxLength; columnIndex++) {
18        // Variable to store the current vertical word
19        let verticalWord: string = '';
20
21        // Loop through each word to form one vertically
22        for (const currentWord of words) {
23            // Add the character at the current index or a space if the word is too short
24            verticalWord += columnIndex < currentWord.length ? currentWord.charAt(columnIndex) : ' ';
25        }
26
27        // Trim the trailing spaces from the current vertical word
28        verticalWord = verticalWord.replace(/\s+$/, '');
29
30        // Add the trimmed vertical word to the result array
31        result.push(verticalWord);
32    }
33
34    // Return the formatted vertical words array
35    return result;
36}
37

Time and Space Complexity

The time complexity of the code can be determined by analyzing the two main operations in the function: splitting the input string into words and forming the vertical print.

  1. Splitting the input string into words takes O(m) time, where m is the length of the input string s, since the split operation goes through the string once.

  2. The main loop runs n times, where n is the maximum length of the words obtained after the split. Inside this loop, forming the temporary list t takes O(k) time for each iteration, where k is the number of words. The while loop inside may run up to k times in the worst-case scenario, which is when all but the first word are shorter than the current index j.

Combining these two points, the overall time complexity is O(m + n*k^2). However, typically the while loop is expected to perform fewer operations as it stops once a non-space character is found from the end. Therefore, the general expected time complexity is O(m + n*k).

The space complexity is determined by the space required to store the words, the ans list, and the temporary list t. The words list will store k words occupying O(m) space (since all words together cannot be longer than the input string s), and the ans list will store at most n * k characters, which accounts for O(n*k) space. The temporary list t requires O(k) space.

Considering these factors, the overall space complexity is O(m + n*k) (since m could be less than or equal to n*k and both need to be considered).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄