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?