Simple Python solution using DFS

  • 1

    We can observe that the rule is to replace substring with length but two consecutive replacement are illegal.

    class Solution(object):
        def generateAbbreviations(self, word):
            res = []
            self.dfs(word, 0, res)
            return res
        def dfs(self, word, index, r):
            for s in xrange(1, len(word) + 1):
                for i in xrange(index, len(word)):
                    if len(word) - i >= s:
                        self.dfs(word[:i]+str(s)+word[i+s:], i+len(str(s))+1, r)

  • 0

    You don't think it's longer than my first one?

  • 0

    Ohh, I didn't find your post before. Sorry about that.

  • 0

    @jedihy What's the runtime for this? Did you try to analyze it?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.