3ms C++ O(num of chars) 97%


  • 0
    E

    This solution is based on ideas from this thread:
    https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution
    Thanks to @kylejao @iaming @Hcisly

    Code can be a little shorter, but I'd rather make sure it's easy to understand

    1. Build a map, where each i show the location from the word start
    2. Start fitting the sentence into the rows, keep track of number of chars left
    3. Also keep track how many sentences we were able to fit until current row.

    At some point (< number of chars in the sentence), we will detect a cycle.
    We can then get the required solution based on:

    1. cycle length
    2. How many cycles we got
    3. Row number where the cycle start (not always the first row)

    Run time: O(n), n number of chars in the sentence.

    class Solution {
    public:
        int wordsTyping(vector<string> sentence, int rows, int cols) {
    	    string s;
        
            for (auto str : sentence)
                s += str + " ";
        
            int len = s.length(), count = 0, pos = 0, i = 0;
        
            vector<int> map(len, 0);
            for (int i = 1; i < len; ++i)
                map[i] = (s[i] == ' ') ? 1 : map[i - 1] - 1;
        
            vector<int> acc;
            unordered_map<int, int> cycles;
        
            while(true) {
                count += cols;
                pos = count % len;
                count += map[pos];
                acc.push_back(count / len);
                if (cycles.count(pos))
                    break;
                cycles[pos] = i++;
            }
        
            int cycleLen = cycles.size() - cycles[pos];
            int cycleRows = rows - (cycles[pos] + 1);
            int cycleStart = cycles[pos];
            
            return (cycleRows / cycleLen) * (acc[i] - acc[cycleStart]) + acc[cycleRows % cycleLen + cycleStart];
        }
    };

Log in to reply
 

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