Java solution based on repeat pattern 15ms


  • 0

    Since the column size is fixed, there is a pattern for each starting word to fit the sentence into one column. For example, when fit ["I", "am", "good" ] to column size of 5:
    when starting with "I", it always fills the column with "I-am-" and has next word "good"
    when starting with "good", it always fills the column with "good-" and next word is "I"
    and keep repeating.
    Since "good" is the last word, when "good" is put into a column, the count of the sentence increase by one.
    When the column size greater than the length of the whole sentence "I-am-good-", we can increase the count by column size divided by the sentence length.

    Time complexity O(n * min(n,rows)), where n is the number of words.

    29ms

    public class Solution {
        Map<Integer, Integer> mem = new HashMap();
        int count(int idx, int[] lens, int sentence_len, int cols){
            int key = idx;
            if (mem.containsKey(key)) return mem.get(key);
            int repeat = cols/sentence_len;
            cols %= sentence_len;
            while (cols >= lens[idx]){
                if (idx==lens.length-1) repeat++;
                cols -= lens[idx]+1;
                idx= (idx+1) % lens.length;
            }
            int ret = repeat * 100 + idx;
            mem.put(key, ret);
            return ret;
        }
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int[] lens = new int[sentence.length];
            int total = 0;
            for (int i=0; i<sentence.length; i++) {
                lens[i] = sentence[i].length();
                total += lens[i]+1;
            }
            int res = 0, idx = 0;
            for (int i=0; i<rows; i++){
                int ret = count( idx, lens, total, cols);
                idx = ret%100;
                res += ret/100;
            }
            return res;
        }
    }
    

    15ms version by replacing HashMap with an array.

    public class Solution {
        int[][] mem;
        int[] count(int idx, int[] lens, int sentence_len, int cols){
            int key = idx;
            if (mem[key] != null ) return mem[key];
            int repeat = cols/sentence_len;
            cols %= sentence_len;
            while (cols >= lens[idx]){
                if (idx==lens.length-1) repeat++;
                cols -= lens[idx]+1;
                idx= (idx+1) % lens.length;
            }
            mem[key] = new int[]{repeat, idx};
            return mem[key];
        }
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int[] lens = new int[sentence.length];
            mem = new int[sentence.length][];
            int total = 0;
            for (int i=0; i<sentence.length; i++) {
                lens[i] = sentence[i].length();
                total += lens[i]+1;
            }
            int res = 0, idx = 0;
            for (int i=0; i<rows; i++){
                int[] ret = count( idx, lens, total, cols);
                idx = ret[1];
                res += ret[0];
            }
            return res;
        }
    }
    

Log in to reply
 

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