JAVA optimized solution 17ms


  • 44

    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;
        }
    };
    

Log in to reply
 

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