[Python知识库]Lintcode 1890 · Form Minimum Number [Python]

Description
Given a pattern str containing only I and D. I for increasing and D for decreasing. Please design an algorithm to return the string that conforms to the pattern and has the smallest dictionary order. Digits from 1 to 9 and digits can’t repeat.

Example
Example 1:

Input:
“D”
Output:
“21”
Explanation:
2>1
Example 2:

Input:
“II”
Output:
“123”
Explanation:
1<2<3
Example 3:

Input:
“DIDI”
Output:
“21435”
Example 4:

Input:
“DDIDDIID”
Output:
“321654798”

题目不难，其数字不重复，其实降低了（思考）复杂度。观察“DIDI”之类的例子，可以知道，每次找到一个I，那从这个I的位置到其左侧最近的I开始，就是一个递减序列。那从哪个数字开始减呢？观察例子可知，这个I如果位于第4位，那从这个I左侧最近的I开始到这个其间最大的数字也就是当前I的位置数，也就是indexof（current I）+ 1，然后，减到少次停下呢？减去当前I到其左侧最近的I的位数。比如两I，相隔2个数字，那就减两次，完成后，更新当下I位置为下一个遇到的I的左侧最近的I位置（LastI）。为了处理方便，一开始就在最后一位加上一个I，方便通用化处理。

class Solution:
    """
    @param str: the pattern 
    @return: the minimum number
    """
    def formMinimumNumber(self, string):
        # Write your code here.
        tempstr = string + 'I'
        curchar = 0
        res = ""
        lastI = 0
        for idx, char in enumerate(tempstr):
            if char == 'I':
                curchar = idx + 1
                while curchar != lastI:
                    res += str(curchar)
                    curchar -= 1
                lastI = idx + 1            
        return res