C++ solution using hashmap, 3ms


  • 1
    T

    Count the words that have been processed, and return count / sentence.size()

    Major optimizations:

    1. Skip duplicate rows
      Use a hash map to record the index in sentence of the first word in each row. Once duplication is found, skip all the remaining duplicate rows
    2. Skip duplicate sentences in a row
      If the sentence can fit into one row, skip duplicate ones.

    The code is not concise, need some suggestions, thanks.

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            unordered_map<int, pair<int, int>> head; // <index of word, pair <row, number of processed word(i)>>
            int n = sentence.size(), i = 0, len = 0;
            bool skip = false;
            for (auto word : sentence) len += word.size();
            for (int c = 0; rows > 0; ++i) {
                int w = i % n;
                if (c == 0) {
                    if (!skip) {
                        if (head.count(w)) { // skip duplicate rows
                            int dr = head[w].first - rows;
                            int di = i - head[w].second;
                            i += rows / dr * di;
                            rows %= dr;
                            if (rows == 0) break;
                            skip = true;
                        }
                        else head[w] = make_pair(rows, i);
                    }
                    i += cols / (len + n) * n; // skip duplicate sentences in a row
                    c = cols - cols % (len + n);
                }
                if (c + sentence[w].size() >= cols) {
                    rows --;
                    if (c + sentence[w].size() > cols) i --;
                    c = 0;
                }
                else c += sentence[w].size() + 1;
            }
            return i / n;
        }
    };
    

Log in to reply
 

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