JAVA optimized solution 17ms


  • 49

    First off, we can easily come up with a brute-force solution. The basic idea of optimized solution is that

    1. sub-problem: if there's a new line which is starting with certain index in sentence, what is the starting index of next line (nextIndex[]). BTW, we compute how many times the pointer in current line passes over the last index (times[]).
    2. relation : ans += times[i], i = nextIndex[i], for _ in 0..<row. where i indicates what is the first word in the current line.

    Time complexity : O(n*(cols/lenAverage)) + O(rows), where n is the length of sentence array, lenAverage is the average length of the words in the input array.

    Well, It's not a typical "DP" problem and I am not even sure it is a "DP" problem. ( ͡° ͜ʖ ͡°)

    public int wordsTyping(String[] sentence, int rows, int cols) {
            int[] nextIndex = new int[sentence.length];
            int[] times = new int[sentence.length];
            for(int i=0;i<sentence.length;i++) {
                int curLen = 0;
                int cur = i;
                int time = 0;
                while(curLen + sentence[cur].length() <= cols) {
                    curLen += sentence[cur++].length()+1;
                    if(cur==sentence.length) {
                        cur = 0;
                        time ++;
                    }
                }
                nextIndex[i] = cur;
                times[i] = time;
            }
            int ans = 0;
            int cur = 0;
            for(int i=0; i<rows; i++) {
                ans += times[cur];
                cur = nextIndex[cur];
            }
            return ans;
        }
    

  • 0
    Y

    @tjcd One possible optimization:
    Within the first for loop, if any word is longer than the length of column, return 0 immediately.


  • 0
    Y

    @tjcd This solution is much better that the others. Suggested!


  • 1
    C

    you know what, I love the final emoji.....BTW, goooood sol


  • 0
    J

    really brilliant solution!


  • 0
    X

    I use a memorized search approach. It sounds similar to your idea. See my post


  • 0
    W

    Good Job! Same idea here. We can improve this solution. When we fill the nextIndex array, we can use two points, so we do not need to start from curLen = 0. Use curLen - sentence[i].length()-1 as the start point of sentence[i] .


  • 0
    K

    Great job! I think this might be the exact idea interviewers would like to hear in a real interview. Optimize your solution based on the BF one.


  • 0
    Y

    @kunge12345 Hi, do you know the time complexity for the brute force one?


  • 0
    H

    @tjcd Great Solution!


  • 0
    K

    @yuan80 I think it is O(rows * (cols / lenAverage)). If lenAverage is much smaller than cols and rows, it is simply O(rows * cols).


  • 0
    Z

    Good solution! I have a similar idea in C++. Another optimization is that when rows >= n+1, there will be two rows starting with the same word, i.e., the sequence repeats with a cycle. We can have a mathematical solution for large rows.
    The run time is O(n^2), even for very large rows and cols. The current run time is 3 ms, beats 96%.

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            // length is total length of sentence, including " ", for the case of large cols
            int n = sentence.size(), length = 0;
            // len is size of each string, dp is repeated sentence times by start of row i
            // mp indicates which word of the sentence is used at the start of row i
            // By at most n+1 row, we will have repeated word at the start of row
            vector<int> len(n, 0), dp(n+1, 0), mp(n, -1);
            for (int i = 0; i < n; i++) {
                len[i] = sentence[i].size();
                length += len[i]+1;
            }
            int ans = 0, cur = 0, k = 0;
            for (; cur < rows; cur++) {
                dp[cur] = ans;
                // if kth string in sentence occurs for the second time, we have a math solution.
                if (mp[k] != -1) {
                    // in every period rows, sentence repeated freq times
                    int prev = mp[k], period = cur-prev, freq = dp[cur]-dp[prev], rm = (rows-cur)%period;
                    return ans + (rows-cur)/period*freq + dp[prev+rm]-dp[prev];
                }
                // kth string at the start of current row 
                mp[k] = cur;
                // dealing with super large cols, which is not included by test cases
                ans += cols/length;
                int j = 0;
                while (j + len[k] <= cols%length) {
                    j += len[k++]+1;
                    if (k == n) {
                        ans++;
                        k = 0;
                    }
                }
            }
            return ans;
        }
    };
    

  • 0
    N

    Great solution! And I think there is an improvement:
    It is not always true that each string could be the starting word of a row. For example:

    sentence: ["as", "df", "qw", "er", "zx", "cv", "gh", "jk", "ty", "ui", "bn", "m"];
    rows = 2;
    cols = 100;
    

    In this example, only times[0]("as") and times[10]("bn") were used.

    It is a waste of time especially when the number of strings in sentence is way bigger than rows.

    So my suggestion is to encapsulate the process of calculating nextIndex and times to a function. And call it as needed. Of course there is a memorization to avoid repeated calculation.


  • 0
    F

    Thanks for the other thought, mine is similar to you but slower than you.
    But I still want to share my thought because it could be better if we change some conditions, which is possibly a kind of follow up question in a real interview.
    The thought is still memory search, I use a hash map which will use the index of sentence as the key, and the value will be if this word performs as the first word in this row, how many words will be filled into this row.
    Then every time we come into a new row, we try to see whether current index is in the hash map or not. If it's in, we just directly retrieve the value and continue; If it's not, we do the iteration to see how many words can be filled in to this row and record it into the cache hash map for the future use.
    I'm confused about the slow time at first, then I see your post. So the basic idea is the same, but you handle with every index first. That makes your time complexity is O(rows) + O(n * (cols / l)), where n is the length of the sentence array and l is the average length of each word in the sentence.While my time complexity is O(rows * (cols / l)). You can see here in the question description, the n is much smaller than rows, but if the follow up question is the rows is pretty small while the sentence is very long, my solution may be an alternative.
    Codes attached:

    class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            Map<Integer, Integer> cache = new HashMap<>();
            int count = 0;
            int n = sentence.length;
            for (int i = 0; i < rows; i++) {
                if (cache.containsKey(count % n)) {
                    count += cache.get(count % n);
                    continue;
                }
                int remain = cols;
                int index = count % n;
                int val = 0;
                while (remain > 0) {
                    if (sentence[count % n].length() <= remain) {
                        remain -= (sentence[count % n].length() + 1);
                        val++;
                        count++;
                    } else {
                        break;
                    }
                }
                cache.put(index, val);
            }
            return count / n;
        }
    }
    

Log in to reply
 

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