A simple simulation


  • 6
    L

    We spend O(n) time on padding each row, resulting in an O(n * rows)-time solution. Here, n denotes the number of sentences.
    Conceptually, each row consists of the following three parts:

    1. a nullable suffix of the given list, followed by
    2. as many as complete given lists, followed by
    3. a nullable proper prefix of the given list

    Part 1 and 3 can be handled by brute-force in O(n) time, and part 2 can be done in O(1) time via a division after we pre-compute the total length of the sentences. Therefore, the overall runtime is O(n * rows).

    public class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int sum = 0, ans = 0, which = 0;
            for (String s : sentence) sum += s.length();
            for (int i = 0; i < rows; i++) {
                int remaining = cols + 1; // reserve an extra space for the dummy space to the left of the first letter
                while (which < sentence.length && sentence[which].length() + 1 <= remaining)
                    remaining -= sentence[which++].length() + 1;
                if (which >= sentence.length) {
                    which = 0;
                    ans = ans + 1 + remaining / (sum + sentence.length);
                    remaining %= sum + sentence.length;
                    while (which < sentence.length && sentence[which].length() + 1 <= remaining)
                        remaining -= sentence[which++].length() + 1;
                }
            }
            return ans;
        }
    }
    

  • 0
    P

    Excellent solution!


  • 4
    Y

    Nice solution! Just for a little bit simplicity, no need to suffix and prefix(for the first while loop in for loop), just count how many whole length and start from last index, see my c++ code

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            int sum = 0;
            for (auto s: sentence) {
                if (s.size() > cols) {
                    return 0;
                }
                sum += s.size()+1;
            }
            int length = sentence.size();
            int index = 0, count = 0;
            for (int i = 0; i < rows; i++) {
                int locations = cols + 1;
                count += locations / sum;
                locations %= sum;
                while (locations >= sentence[index].size() + 1) {
                    locations -= sentence[index++].size() + 1;
                    if (index == length) {
                        count++;
                        index = 0;
                    }
                }
            }
            return count;
        }
    };
    

  • 0
    J

    If you compute a running sum of the lengths of the words in a sentence, it seems like you can use binary search to find how many words in the prefix and suffix sentence you can add, using the number of columns left as a key.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.