320.Generalized Abbreviation

Tags: [DFS], [backtracking], [set], [two_choice]

Com: {g}

Link: https://leetcode.com/problems/generalized-abbreviation/#/description

Write a function to generate the generalized abbreviations of a word.

Example:

Given word ="word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Better Solution: DFS, Backtracking

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        if not word:
            return ['']

        result = []
        buff = []
        self.helper(word, 0, 0, buff, result)
        return result

    def helper(self, word, index, counter, buff, result):
        # base case
        if index >= len(word):
            if counter:
                buff.append(str(counter))

            result.append(''.join(buff))
            if counter:
                buff.pop()
            return

        # choice 1: encode
        self.helper(word, index + 1, counter + 1, buff, result)

        # choice 2: do not encode
        if counter:
            buff.append(str(counter))
        buff.append(word[index])
        self.helper(word, index + 1, 0, buff, result)
        buff.pop()
        if counter:
            buff.pop()

Revelation:

• If we choose the choice 2, do not forget to reset the counter to 0.
• There is no duplicates, because for example, if we want to get the 'word' in the result, the only way we can do is keeping choosing the choice 2.
• For the word whose length = n, there are 2^n abbreviations.

Note:

• Time complexity = O(2^n), n is the length of the given word.

Solution: DFS, Backtracking, Set, Two Choice

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        if not word:
            return ['']

        result = set()
        buff = []
        self.generate_abbreviations_helper(word, 0, buff, result)
        return list(result)

    def generate_abbreviations_helper(self, word, index, buff, result):
        # base case
        if index >= len(word):
            result.add(''.join(buff))
            return

        for i in xrange(index, len(word)):
            # choice 1: encode word[index:i + 1]
            buff.append(str(i - index + 1))
            if i + 1 < len(word):
                buff.append(word[i + 1])
            self.generate_abbreviations_helper(word, i + 2, buff, result)
            if i + 1 < len(word):
                buff.pop()
            buff.pop()

            # choice 2: do not encode word[index:i + 1]
            buff.append(word[index:i + 1])
            self.generate_abbreviations_helper(word, i + 1, buff, result)
            buff.pop()

Revelation:

• The abbreviations include the word itself.
• Make result as a set to remove the duplicates. For example, if we don't do dedup, there will be multiple "word" in the result, because, to get the 'word' in the result, during the whole process, we have to choose the choice 2, but there are many ways to keep choosing choice 2, for example, we can first choose not encode 'w' then next level recursion, we can choose not encode 'ord', or on the first level recursion, we choose not encoding 'wor', and in the next level recursion, we choose not encode 'rd'.
• There are 2^n abbreviations, but the time complexity of this algorithm = O(n!), so there must exist the duplicates.

Note:

• Time complexity = O(n!), n is the length of the given word.