# Word Wrap Problem

Jul 1st, 2022 (edited)
720
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.