LC320. Generalized Abbreviation

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        """ tc O(N*2^N)    sc O(N) for path space      
        """
        res = []
        
        def dfs(pos,path, cnt):
            if pos == len(word):
                if cnt > 0:
                    path.append(str(cnt))
                res.append(''.join(path))
            else:
                # put current cnt into path 
                dfs(pos+1,path+[str(cnt) if cnt else ""] + [word[pos]], 0 )
                # not put
                dfs(pos+1,path, cnt+1 )
        dfs(0,[],0)
        return res