lc418

發表於   |   分類於   |   0 comments   |  

Given a rows x cols screen and a sentence represented by a list of words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won’t exceed 100.
Length of each word won’t exceed 10.
1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = [“hello”, “world”]

Output:
1

Explanation:
hello—
world—

The character ‘-‘ signifies an empty space on the screen.
Example 2:

Input:
rows = 3, cols = 6, sentence = [“a”, “bcd”, “e”]

Output:
2

Explanation:
a-bcd-
e-a—
bcd-e-

The character ‘-‘ signifies an empty space on the screen.
Example 3:

Input:
rows = 4, cols = 5, sentence = [“I”, “had”, “apple”, “pie”]

Output:
1

Explanation:
I-had
apple
pie-I
had–

The character ‘-‘ signifies an empty space on the screen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int cur_len = 0;
        int num_words = sentence.size();
        for (auto s: sentence) {
            if (s.length() > cols)
                return 0;
        }
        vector<int> vv(num_words, 0);
        for (int j = 0; j < num_words; j++) {
            cur_len = 0;
            for (int i = j; sentence[i].length()+cur_len<=cols; i=(i+1)%num_words) {
                cur_len+=sentence[i].length()+1;
                vv[j]++;
            }
        }
        int k = 0;
        int m = 0;
        for (int j = 0; j < rows; j++) {
            m += vv[k];
            k = (k+vv[k]) % num_words;
        }
        int res = m/num_words;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int num_words = sentence.size();
        for (auto s: sentence) {
            if (s.length() > cols)
                return 0;
        }
        vector<int> vv(num_words, -1);
        
        int k = 0;
        int m = 0;
        for (int j = 0; j < rows; j++) {
            if (vv[k] == -1) {
                int cur_len = 0;
                vv[k]++;
                for (int i = k; sentence[i].length()+cur_len<=cols; i=(i+1)%num_words) {
                    cur_len+=sentence[i].length()+1;
                    vv[k]++;
                }
            }
            m += vv[k];
            k = (k+vv[k]) % num_words;
        }
        int res = m/num_words;
        return res;
    }
};

Dec 8 update:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int len = sentence.size();
        if (!len) return 0;
        vector<int> mp(len, 0);
        int cur = 0;
        int total = 0;
        for (int row = 0; row < rows; row++) {
            int cur_len = 0;
            int slen;
            if (!mp[cur]) {
                for (int j = cur; cur_len + (slen=sentence[j].length()) <= cols; j=j+1-((j+1)>=len?len:0)) {
                    cur_len += slen+1;
                    mp[cur]++;
                }
            }
            total += mp[cur];
            cur = (mp[cur]+cur)%len;
            // cout << cur << " " << mp[cur] << " " <<total<< endl;
        }
        return total/len;
    }
};