Why tagged hard? Simple C++ solution


  • 2

    I thought I must be missing something because the problem seems rather easy, but then I did just this:

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            vector<int> wc(sentence.size(), 0);
            for (size_t i = 0; i < sentence.size(); ++i) {
                wc[i] = wordsFit(sentence, i, cols);
            }
            int words = 0, start = 0;
            for (int i = 0; i < rows; ++i) {
                words += wc[start];
                start = (start + wc[start]) % sentence.size();
            }
            return words / sentence.size();
        }
    private:
        static int wordsFit(const vector<string> &sentence, size_t start, int cols) {
            if (sentence[start].size() > cols)
                return 0;
            int sum = sentence[start].size(), count = 1;
            for (size_t i = (start + 1) % sentence.size(); ; i = (i + 1) % sentence.size()) {
                if (sum + 1 + sentence[i].size() > cols)
                    return count;
                sum += 1 + sentence[i].size();
                ++count;
            }
        }
    };
    

    And it only got accepted on the second try because I made a stupid mistake first time. Moreover, it's far from optimal because once the main loop enters the repeating pattern, there is no point to run it for thousands of lines. You could easily calculate the number of repetitions and jump almost to the very end. I didn't even do that.

    I found the previous two problems to be much harder.


  • 0

    Hi, actually range of rows and cols should be set to 10^12. But I thought that was too hard so rows and cols were eliminated to 10000. Sorry for misleading.


Log in to reply
 

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