423.Reconstruct Original Digits from English

Tags: [trick]

Link: https://leetcode.com/problems/reconstruct-original-digits-from-english/?tab=Description

Given anon-emptystring containing an out-of-order English representation of digits0-9, output the digits in ascending order.

Note:

1. Input contains only lowercase English letters.
2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"
Output: "012"

Example 2:

Input: "fviefuro"
Output: "45"

Solution: find trick

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return s

        counting = [0 for _ in xrange(26)]
        for c in s:
            counting[ord(c) - ord('a')] += 1

        nums = [0 for _ in xrange(10)]
        nums[0] = self.get_num_of_chars(counting, 'z')
        nums[2] = self.get_num_of_chars(counting, 'w')
        nums[4] = self.get_num_of_chars(counting, 'u')
        nums[5] = self.get_num_of_chars(counting, 'f') - nums[4]
        nums[7] = self.get_num_of_chars(counting, 'v') - nums[5]
        nums[6] = self.get_num_of_chars(counting, 's') - nums[7]
        nums[1] = self.get_num_of_chars(counting, 'o') - nums[0] - nums[2] - nums[4]
        nums[3] = self.get_num_of_chars(counting, 'r') - nums[0] - nums[4]
        nums[8] = self.get_num_of_chars(counting, 't') - nums[2] - nums[3]
        nums[9] = self.get_num_of_chars(counting, 'i') - nums[5] - nums[6] - nums[8]

        buff = []
        for num in xrange(10):
            counter = nums[num]
            for _ in xrange(counter):
                buff.append(str(num))

        return ''.join(buff)

    @staticmethod
    def get_num_of_chars(counting, c):
        return counting[ord(c) - ord('a')]

Revelation:

• zero, one, two, three, four, five, six, seven, eight, nine, some of the numbers contains the unique characters, for example, once we know the number of character 'z', we know the number of 'zero', and the remaining numbers can be calculated by the similar way.

Note:

• Time complexity = O(n), n is the number of characters in the given string.

Time Limited Exceed

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return s

        digits = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
        char_counting_map = {}
        for c in s:
            if c in char_counting_map:
                char_counting_map[c] += 1
            else:
                char_counting_map[c] = 1

        result = []
        buff = []
        self.original_digits_helper(char_counting_map, digits, result, buff)

        if result:
            return result[0]
        else:
            return ''

    def original_digits_helper(self, char_counting_map, digits, result, buff):
        # base case
        if self.use_out_of_chars(char_counting_map):
            result.append(''.join(buff))
            return

        for i in xrange(len(digits)):
            if not self.can_build_digit(char_counting_map, digits[i]):
                continue

            for c in digits[i]:
                char_counting_map[c] -= 1
            buff.append(str(i))

            # recursion
            self.original_digits_helper(char_counting_map, digits, result, buff)

            buff.pop()
            for c in digits[i]:
                char_counting_map[c] += 1

    @staticmethod
    def use_out_of_chars(char_counting_map):
        for key in char_counting_map:
            if char_counting_map[key] > 0:
                return False
        return True

    @staticmethod
    def can_build_digit(char_counting_map, digit):
        digit_c_counting_map = {}
        for c in digit:
            if c in digit_c_counting_map:
                digit_c_counting_map[c] += 1
            else:
                digit_c_counting_map[c] = 1

        for key in digit_c_counting_map:
            if key not in char_counting_map or digit_c_counting_map[key] > char_counting_map[key]:
                return False
        return True

Revelation:

• Brute-force: try all possible ways to use the givens characters to build the digits.

Note:

• Time complexity = O(n) + O(10^k) = O(n + 10^k), k <= n, n is the number of characters in the given string, k is the number of the digits of the built number(result).