Java 6ms, basically try to find periods


  • 0
    F
    public class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int[] lens = new int[2 * sentence.length];
            int sum = 0;
            for(int i = 0; i< lens.length; i++){
                int templen = sentence[i%sentence.length].length();
                if(templen > cols) return 0;
                lens[i] = sum += templen + 1;
            }
            sum /= 2;
            Map<Integer, int[]> map = new HashMap<>();
            List<Integer> heads = new ArrayList<>();
            int s = 0;
            int total = 0;
            map.put(s, new int[]{0,0});  // ith line has k sentences before ith line;
            heads.add(s);
            for(int i = 0; i < rows; i++){
                int c = cols;
                c -= sentence[s].length();
                total += c/sum;
                c = (c % sum);
                int ind = Arrays.binarySearch(lens, s + 1, lens.length, lens[s] + c);
                if(ind < 0) ind = -ind - 1;
                else ind++;
                if(ind >= sentence.length) total++;
                s = ind % sentence.length;
                if(map.containsKey(s)){
                    int period = i + 1 - map.get(s)[0];
                    int cycles = (rows - map.get(s)[0]) / period;
                    int newhead = (rows - map.get(s)[0])% period + map.get(s)[0];
                    return cycles * (total - map.get(s)[1]) + map.get(heads.get(newhead))[1];
                }else{
                    int[] value = new int[]{i + 1, total};
                    map.put(s, value);
                    heads.add(s);
                }
            }
            return map.get(heads.get(heads.size() - 1))[1];
        }
    }
    

Log in to reply
 

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