C++ 6ms Jump through possible rows and cols

  • 0

    The basic idea is using hashmap to record the word which appeard at the very beginning of a row. If that word appeared again at the beginning of another row, that means the whole sentence finished several cycles between these two rows, but with the first idx of that word, instead of 0.

    for example, with the words "a, bcd, hello", if "bcd" idx = 1 appeared at the beginning of row i and row j
    we know that the sentence must have cycled several times between row i, and row j-1. Since we recorded the number of times (cnt )that "bcd" appeared, we know that the whole sentence cycled cnt times. And it will continue to recycle cnt times for every j-i rows. So the total cycled times should be the sum of cycled times before the second appearance of "bcd"', plus the (loop times * cnt ) and how many cycles will be fitted to the remaining grid.

    class Solution {
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            int n = sentence.size();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += sentence[i].size() + 1;
            // record the idx which appeard at the begining of a row, it's lineNo and appeared Times
            unordered_map<int, pair<int, int>> idxmap;
            int idx = 0;
            int i = 0;
            int times = 0;
            bool found_repeator = false;
            while (i < rows) {
                int j = 0;
                // an idx appeard second time at the very begining.
                if (idxmap.count(idx%n) && !found_repeator) {
                    int cnt = idxmap[idx%n].first;
                    int lineNo = idxmap[idx%n].second;
                    // appeared second time means recycle 
                    // so count how many times the sentence appeard during recycle
                    times += (rows - i) / (i - lineNo) * cnt;
                    i += (rows - i) / (i - lineNo) * (i - lineNo);
                    found_repeator = true;
                // record the idx appeard at begining
                if (!idxmap.count(idx%n)) {
                    idxmap[idx%n] = make_pair(0, i);
                // how many times appeard before or after recycle
                j += cols/ sum * sum;
                times += (cols/sum );
                for (auto it = idxmap.begin(); it != idxmap.end(); it++) {
                    it->second.first += cols/sum;
                while (j < cols && cols - j >= sentence[idx%n].size()) {
                    j += sentence[idx%n].size() + 1;
                    if (idxmap.count(idx%n)) idxmap[idx%n].first++;
                    if (idx % n == 0) times++;
            return times;

Log in to reply

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