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?