Simple C++ solution optimized by some arithmetic


  • 0
    K

    Simple algorithm.

    1. Skip to the point in the current column where the sentence won't fit in the same row anymore.
    2. Once we have r rows fully (all columns in those rows as well) filled by k repetition of sentence, we know every following r rows will have k repetitions. Skip to the last total_rows % r rows.

    Worst Case Complexity: O(n*frows)
    n is total length of the sentence
    frows is min # of rows to fully contain k sentence repetitions

    Commented as much as possible.

        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            
            int i = 0, j = 0; // row and column pointers
            int res = 0; // total repetitions
            
            int total_size = 0; // total size of sentence
            for (string& s : sentence) {
                total_size += s.size();
            }
            
            while (i < rows && j < cols) {
                int s = 0; // index into sentence vector
                
                // skip to the column where splitting of the sentence takes place
                int occupied_size = total_size + sentence.size(); // with spaces
                int repeat_in_row = (cols - j)/occupied_size; // repetitions
                res += repeat_in_row;
                j += repeat_in_row * occupied_size; // remaining column
                if (j == cols) {
                    ++i; j = 0; // move to the next row
                    --res; // hack to let the later if statement to handle ++res
                    s = sentence.size(); // we are done with the sentence
                }
                
                // this is to go over multiple rows for a single sentence iteration
                while (s < sentence.size() && i < rows && j < cols) {
                    int n = sentence[s].size();
                    if (j + n > cols) { // doesn't fit
                        ++i;
                        j = 0;
                    } else if ((j + n == cols) || (j + n == cols - 1)) { // just fits or just fits with space
                        ++i;
                        j = 0;
                        ++s;
                    } else { // fits
                        j += n + 1;
                        ++s;
                    }
                }
                
                // only add if we successfully finished adding all the strings
                if (s == sentence.size()) {
                    ++res;
                    if (j == 0) { // end of column
                        res *= rows/i; // repeat total res as many i sized rows as possible
                        i = rows - rows%i; // remaining rows
                    }
                } else {
                    break;
                }
            }
            
            return res;
        }
    

Log in to reply
 

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