Leetcode 418. Sentence Screen Fitting

Problem Explanation

In this problem, we are given a screen with rows x cols and a list of words in a sentence. Now, we have to count how many times we can fit the sentence within the screen.

We are to consider the following rules:

• A word cannot be broken into two lines.
• The order of the words in the sentence must remain unchanged.
• Two consecutive words in a line should be separated by a single space.
• Total words in the sentence won't exceed 100.
• Length of each word is greater than 0 and won't exceed 10.
• 1 ≤ rows, cols ≤ 20,000.

For instance, consider the sentence ["hello", "world"] and a screen of 2 rows and 8 cols. Then the sentence can be fitted in the screen by writing "hello" on the first line and "world" on the second line. Here '---' denotes an empty space on the screen. Therefore, the sentence can be fitted on the screen 1 time.

Solution Explanation

First, we combine the words of the sentence together along with space (resulting in the combined string).

Then, we start filling the sentence from the top left of the screen. While we still have rows left, we keep adding cols to i until we can no longer do so. If our current position is a space, it implies we were able to fit a word exactly up to the end of the line so we skip the space and move to the next position. If our current position is not a space, we iterate back until we reach the start of the current word.

Finally, we return the count of the sentence that fit on the screen. This is obtained by doing integer division of i by the length of the combined string.

Python Solution

1
2python
3class Solution:
4    def wordsTyping(self, sentence, rows, cols):
5        # join all words together with space
6        combined = " ".join(sentence) + " "
7        n = len(combined)
8        i = 0
9        
10        while rows:
11            # we may able to fit in current row up to point i
12            i += cols 
13            
14            # if latest character is space, we can fit without problem, skip space and go next
15            if combined[i % n] == " ":
16                i += 1
17            else:
18                # if latest character is not space, means our word is incomplete, trace back till we find space
19                while i > 0 and combined[(i - 1) % n] != " ":
20                    i -= 1
21            # decrement rows as we just processed a row
22            rows -= 1
23
24        # number of cycles of combined string that could fit inside screen
25        return i // n 

Java Solution

1
2java
3public class Solution {
4    public int wordsTyping(String[] sentence, int rows, int cols) {
5        String combined = String.join(" ", sentence) + " ";
6        int n = combined.length();
7        int i = 0;
8
9        while (rows-- > 0) {
10            i += cols;
11
12            if (combined.charAt(i % n) == ' ') {
13                i++;
14            } else {
15                while (i > 0 && combined.charAt((i - 1) % n) != ' ') {
16                    i--;
17                }
18            }
19        }
20
21        return i / n;
22    }
23}

JavaScript Solution

1
2javascript
3class Solution {
4    wordsTyping(sentence, rows, cols) {
5        let combined = sentence.join(" ") + " ";
6        let n = combined.length;
7        let i = 0;
8
9        while (rows--) {
10            i += cols;
11
12            if (combined[i % n] === ' ') {
13                i++;
14            } else {
15                while (i > 0 && combined[(i - 1) % n] !== ' ') {
16                    i--;
17                }
18            }
19        }
20
21        return Math.floor(i / n);
22    }
23}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int wordsTyping(vector<string>& sentence, int rows, int cols) {
6        string combined = accumulate(sentence.begin(), sentence.end(), string(""), [](string& s, string& word){ return s + word + " "; });
7        int n = combined.size();
8        int i = 0;
9      
10        while (rows--) {
11            i += cols;
12
13            if (combined[i % n] == ' ') {
14                i++;
15            } else {
16                while (i > 0 && combined[(i - 1) % n] != ' ') {
17                    i--;
18                }
19            }
20        }
21
22        return i / n;
23    }
24};

C# Solution

1
2c#
3public class Solution {
4    public int WordsTyping(string[] sentence, int rows, int cols) {
5        string combined = String.Join(" ", sentence) + " ";
6        int n = combined.Length;
7        int i = 0;
8        
9        while (rows-- > 0) {
10            i += cols;
11
12            if (combined[i % n] == ' ') {
13                i++;
14            } else {
15                while (i > 0 && combined[(i - 1) % n] != ' ') {
16                    i--;
17                }
18            }
19        }
20
21        return i / n;
22    }
23}

The solutions provided above work across multiple well-known languages such as Python, Java, JavaScript, C++, and C#. As seen, the primary idea behind the solution remains the same across these languages.

The combined string holds all the words from the sentence along with spaces. Then, we calculate how many sentences (as i // n), we can fit into the screen. To satisfy the condition that no word should break in between and must be in the same order, we only count complete words (moving back to the beginning if it's incomplete) and maintain the same sequence as in the original sentence.

Test these solutions with different sentences and screen sizes to understand how they work. Remember, the length of each word should be 0 or less and won't exceed 10. The total words in the sentence should not exceed 100, and the values of rows and cols must be between 1 and 20,000. Always consider edge cases while testing. Make sure to thoroughly understand the problem statement and the solution logic before attempting to code. Practice and perseverance are the key to mastering data structures and algorithms. Happy Coding!