484.Find Permutation

Tags: [permutation], [lexicographically], [string], [reverse], [greedy], [trick]

Com: {g}

Link: https://leetcode.com/problems/find-permutation/\#/description

By now, you are given a secret signature consisting of character 'D' and 'I'. 'D' represents a decreasing relationship between two numbers, 'I' represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature "DI" can be constructed by array [2,1,3] or [3,1,2], but won't be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can't represent the "DI"secret signature.

On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, ... n] could refer to the given secret signature in the input.

Example 1:

Input: "I"
Output:
 [1,2]

Explanation:
 [1,2] is the only legal initial spectial string can construct secret signature "I", where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: "DI"
Output:
 [2,1,3]

Explanation:
 Both [2,1,3] and [3,1,2] can construct the secret signature "DI", 

but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3]

Note:

The input string will only contain the character 'D' and 'I'.

The length of input string is a positive integer and will not exceed 10,000

Solution: Reverse

class Solution(object):
    def findPermutation(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        if not s:
            return [1]

        rest = [x for x in xrange(1, len(s) + 2)]
        i = 0
        while i < len(s):
            c = s[i]
            if c == 'D':
                end = i
                while end < len(s) and s[end] == 'D':
                    end += 1

                # if s[i:end] (not including end) contains all 'D',
                # then we should reverse rest from i to end (including end).
                self.reverse(rest, i, end)
                i = end
                continue
            i += 1

        return rest

    def reverse(self, arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

Revelation:

• 在s中遇到连续的D的序列，例如s[3:7] (不包括index = 7) 中都是‘D’， 那么就reverse rest[3:8](包括index = 7，不包括index = 8), reverse 完后s的index指到8(即第一个不是'D'的char)，遇到‘I’ 就略过.
• 为什么这个算法是对的，原因是，一开始rest是从小到大sorted的，遇到'I'我们不做任何处理，遇到‘D’ sub str时，就reverse相应的rest，即便这个‘D’ sub str前有‘I’， 因为这个sub str ‘D’ 在‘I’ 之后，所以不管reverse与不reverse这部分的rest都比前面的大，所以这就保证了‘I’ 的正确性，reverse 的 这段rest保证了‘D’ 的正确性，如果之后有‘I’， 因为这段‘D’ 对应的rest在后面 ‘I’ 对应的rest之前，所以这段‘D’ 对应的 rest都比后面‘I’ 对应的rest 小，这也就保证了后面的‘I’ 的正确性.

Note:

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