LeetCode 418: Sentence Screen Fitting Solution

Master LeetCode problem 418 (Sentence Screen Fitting), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

418. Sentence Screen Fitting

Medium

Array String Dynamic Programming

Problem Explanation

Explanation

The problem asks us to find how many times a given list of words can be fitted on a screen with a given number of rows and columns. We need to fit as many complete sentences as possible, where each sentence is constructed by appending words sequentially until the screen is filled.

To solve this problem, we need to iterate through each row on the screen and keep track of the current index of the word list. We simulate the process of fitting words on the screen by calculating the number of complete sentences that can be formed.

Algorithm

Initialize a variable wordsIndex to keep track of the current index in the list of words.
Iterate through each row of the screen:
- Initialize a variable col to represent the current column position.
- While there is enough space on the current row to fit a word from the list:
  - Calculate the remaining space on the row after fitting a word.
  - If the remaining space is less than the length of the current word, break out of the loop.
  - Otherwise, increment the col by the length of the word and move to the next word in the list.
  - If we reach the end of the list, increment the number of sentences fitted and reset the wordsIndex to 0.
Return the total number of sentences fitted on the screen.

Time Complexity

The time complexity of this algorithm is O(rows + words.length), where rows is the number of rows on the screen and words is the list of words.

Space Complexity

The space complexity of this algorithm is O(1) as we are using constant extra space.

Solution Code

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int wordsIndex = 0;
        int sentenceCount = 0;

        for (int i = 0; i < rows; i++) {
            int col = 0;
            while (col + sentence[wordsIndex].length() <= cols) {
                col += sentence[wordsIndex].length() + 1;
                wordsIndex++;
                if (wordsIndex == sentence.length) {
                    sentenceCount++;
                    wordsIndex = 0;
                }
            }
        }

        return sentenceCount;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 418 (Sentence Screen Fitting)?

This page provides optimized solutions for LeetCode problem 418 (Sentence Screen Fitting) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 418 (Sentence Screen Fitting)?

The time complexity for LeetCode 418 (Sentence Screen Fitting) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 418 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 418 in Java, C++, or Python.

Back to LeetCode Solutions