C++ memorized search


  • 12
    X

    I use num to represent how many words can be put in the screen. we use a map<i, cnt> to record for each line how many words cnt can be put when starting with word i. So when we scan each line of the screen, we first get the starting word should be put on this line. If this starting words is already in the map, then just read it; otherwise, create a new entry in this map.

        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            unordered_map<int, int> umap;
            int num = 0, n = sentence.size();
            for(int i = 0; i < rows; i++){
                int start = num % n;
                if(umap.count(start) == 0){
                    int cnt = 0, len = 0;
                    for(int i = start; len < cols; i = (i+1) % n, cnt++){
                        if(len + sentence[i].size() > cols)
                            break;
                        len += sentence[i].size() + 1;
                    }
                    num += cnt;
                    umap.emplace(start, cnt);
                }
                else
                    num += umap[start];
            }
            return num / n;
        }
    

  • 1
    X

    We can replace the unordered_map with a vector<int> umap(n, -1), which has a better performance.


  • 2

    Concise and elegant solution!
    Nice Job!

    It can be more concisely in this way.

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            int n = sentence.size(), num = 0, start = 0;
            unordered_map<int, int> mp;
            while (rows--) {
                start = num % n;
                if (mp.find(start) == mp.end()) {
                    int cnt = 0, len = -1;
                    while ((len = len + 1 + (int)sentence[(start + cnt) % n].size()) <= cols)
                        cnt++;
                    mp[start] = cnt;
                }
                num += mp[start];
            }
            return num / n;
        }
    };
    

  • 1
    G

    @yong.cao.7731
    Moreover, it can be more concise as just going one step 4ward. :P

    if (mp.find(start) == mp.end()) {
                    int cnt = 0, len = -1;
                    while ((len += 1 + (int)sentence[(start + cnt++) % n].size()) <= cols);
                    mp[start] = cnt;
                }

Log in to reply
 

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