Java, 10ms, starting with 12ms-java-solution-using-dp but then using a binary progression


  • 5
    E

    Using the very elegant solution, https://discuss.leetcode.com/topic/65173/12ms-java-solution-using-dp
    I shaved off 2 ms by using a binary progression rather than linear.
    If w = # of words, then this is O(w * cols + w * log(rows)) instead of O(w*cols + rows)
    If a word w starts a line, we have an array that computes which word starts the next line.
    Then, we turn it into an array that computes which word starts the next next line.
    Then, we turn it into an array that computes which word starts the next next next next line.
    and so on.

    
    // starting point:  https://discuss.leetcode.com/topic/65173/12ms-java-solution-using-dp
    public class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int n = sentence.length;
            int[] nextWord = new int[n];
    
            int len = 0;
            int word = 0;
            for (int i = 0; i < n; i++) {
                // remove the length of previous word and space
                if(i != 0 && len > 0) len -= sentence[i - 1].length() + 1;
                // calculate the start of next line.
                // it's OK the index is beyond the length of array so that 
                // we can use it to count how many words one row has.
                while(len + sentence[word % n].length() <= cols) len += sentence[word++ % n].length() + 1;
                nextWord[i] = word;
            }
            int[] nextWordPow = new int[n];
            int[] swap;
            int count = 0;
            int k = 0;
            for (int pow = 1; pow <= rows; pow <<= 1) {
                if ((pow & rows) != 0) {
                    count += nextWord[k] - k;
                    k = nextWord[k] % n;
                }
                for (int i = 0; i < n; i++) {
                    int nextLineWord = nextWord[i];
                    int nextLineWordMod = nextLineWord % n;
                    int nextNextLineWord = nextWord[nextLineWordMod] - (nextLineWordMod) + nextLineWord;
                    nextWordPow[i] = nextNextLineWord;
                }
                swap = nextWord;
                nextWord = nextWordPow;
                nextWordPow = swap;
            }
            // divide by the number of words in sentence
            return count / n;
        }
    }
    

  • 0
    C

    +1 for the idea. Totally brilliant and I have not thought of that


  • 0
    G

    Can you explain what this snippet means?

        if ((pow & rows) != 0) {
                    count += nextWord[k] - k;
                    k = nextWord[k] % n;
                }

Log in to reply
 

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