SRM497 - div2 - level two

srm497_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM497 - div2 - level two
The signature of a permutation is a string that is 
computed as follows: for each pair of consecutive elements 
of the permutation, write down the letter 'I' (increasing) 
if the second element is greater than the first one, 
otherwise write down the letter 'D' (decreasing).

For example, the signature of the permutation {3,1,2,7,4,6,5} 
is "DIIDID".

Your task is to reverse this computation: You are given a 
String signature containing the signature of a permutation. 
Find and return the lexicographically smallest permutation 
with the given signature. If no such permutation exists, 
return an empty int[] instead. 

Definition:
    Class: PermutationSignature
    Method: reconstruct
    Parameters: String
    Returns: int[]
    Method signature: int[] reconstruct(String signature)

Notes
    - For any positive integer N, a permutation of N elements 
      is a sequence of length N that contains each of the integers 
      1 through N exactly once.
    - To compare two permutations A and B, find the smallest 
      index i such that A[i] and B[i] differ. If A[i] < B[i], 
      we say that A is lexicographically smaller than B, 
      and vice versa.
"""

class PermutationSignature(object):
    """Permutation Signature

    Constraints:
        - signature will contain between 1 and 50 characters, 
          inclusive.
        - Each character in signature will be either 'I' or 'D'.

    >>> permutation = PermutationSignature()
    >>> print permutation.reconstruct('IIIII')
    [1, 2, 3, 4, 5, 6]
    >>> print permutation.reconstruct('DI')
    [2, 1, 3]
    >>> print permutation.reconstruct('IIIID')
    [1, 2, 3, 4, 6, 5]
    >>> print permutation.reconstruct('DIIDID')
    [2, 1, 3, 5, 4, 7, 6]
    >>> print permutation.reconstruct('DDDDDD')
    [7, 6, 5, 4, 3, 2, 1]
    """

    def __init__(self):
        pass

    def reconstruct(self, signature):
        res = [i + 1 for i in range(len(signature) + 1)]
        dfrom = -1
        for i in range(len(signature)):
            if (signature[i] == 'I' and dfrom != -1):
                rev = res[dfrom:i+1]
                rev.reverse()
                res = res[:dfrom] + rev + res[(i+1):]
                dfrom = -1
            elif signature[i] == 'D' and i >= len(signature)-1:
                # For ended in 'D'
                rev = res[(dfrom == -1 and i or dfrom):]
                rev.reverse()
                res = res[:(dfrom == -1 and i or dfrom)] + rev
            elif signature[i] == 'D' and dfrom == -1:
                dfrom = i
        return res

if __name__ == '__main__':
    import doctest
    doctest.testmod()