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