So I was doing this problem on leetcode.
I was doing in python. This is my code
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
ans = [];cur = []
def rec(index):
if index==len(s):
ans.append(''.join((cur[:])).strip())
return
for i in range(index,len(s)):
if s[index:i+1] in wordDict:
cur.append(" ")
cur.append(s[index:i+1])
rec(i+1)
cur.pop(-1)
cur.pop(-1)
rec(0)
return ans
On the for loop,
if s[index:i+1] in wordDict:
This creates a copy of string s from the index till i+1 and hence takes O(n) time. If i use string concatenation instead of this, the time complexity will be O(n^2) as strings are immutable in python . I could'nt use list as keys cannot be mutable in dictonary. So what should I do to make the for loop linear time complexity? Is there any way to make the string concatenation linear in python?
you can covert list to tuple to use it in dictionary like this :wordDict[tuple([1,2,3])] because tuple is immutable