Advertisement
Iam_Sandeep

Word Wrap Problem

Jul 1st, 2022 (edited)
820
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.10 KB | None | 0 0
  1. import sys
  2. sys.setrecursionlimit(10**9)
  3. from functools import lru_cache
  4. class Solution:
  5.     def solveWordWrap(self, nums, k):
  6.         @lru_cache()
  7.         def help(c,i):#c points to the index where word can be started
  8.             l=nums[i]
  9.             ans=float('inf')
  10.             rem=k-c#rem shows remaining valid length available . It means it avoids extra space when there is already another word
  11.             if i==n-1:#If reached last word. Just ignore remaining spaces .Since it is end of line
  12.                 if l<=rem:#If we can insert return 0
  13.                     return 0
  14.                 return (1+rem)**2 #Take new line return the remaining wasted space after (n-1) word
  15.             if l<=rem: #If we can insert add word
  16.                ans=min(ans,help(c+l+1,i+1)) # we are pointing next valid location in the line where new word can start
  17.             if c!=0:#Not a Fresh line i.e. already some words are there
  18.                 ans=min(ans,help(0,i)+(1+rem)**2) #add space waste. Here I am adding (rem+1)**2 not rem**2 (think..)
  19.             return ans
  20.         return help(0,0)
  21.                
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement