6ms cpp solution


  • 0

    Here's my solution, it's a very straightforward idea when cols and rows are small and use two tricks to optimize:

    1. If cols is larger than the least total length of n round, we can directly add n to ret, and set cols to cols%roundsum.
    2. Cache the next line's start word's index, if it's smaller than current index, ret++.
    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            if(sentence.empty()) return -1;
            vector<int> rec(sentence.size(),-1), q;
            int sz = sentence.size(), ret = 0, rest;
            int roundsum = 0, i = 0, start = 0;
            for(int i = 0; i< sz; i++) {
                q.push_back((int)sentence[i].size());
                roundsum+=sentence[i].size()+1;
            }
            if(cols%roundsum==roundsum-1) return (cols+1)/roundsum*rows;
            ret+=(cols/roundsum)*rows;
            cols %=roundsum;
            rest = cols;
            while(rows){
                if(rest==cols&&rec[i]>=0){
                    if(rec[i]<i) ret++;
                    rows--;
                    i = rec[i];
                }else if(q[i]<=rest){
                    rest-=q[i];
                    if(rest) rest--;
                    if(++i==sz){
                        ret++;
                        i = 0;
                    }
                }else{
                    rest = cols;
                    rows--;
                    rec[start] = i;
                    start = i;
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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