1-liner and 5-liner, visual explanation


  • 28

    If it's all just I, then the answer is the numbers in ascending order. And if there are streaks of D, then just reverse the number streak under each:

    0_1485039424299_Find Permutation.png

    My 5-liner does exactly that. Start from sorted, then find the D-streaks and reverse the numbers under them:

    def findPermutation(self, s):
        a = range(1, len(s) + 2)
        for m in re.finditer('D+', s):
            i, j = m.start(), m.end() + 1
            a[i:j] = a[i:j][::-1]
        return a
    

    My 1-liner tells sorted that the (larger) number i comes before the (smaller) number j iff they're both under the same D-streak, i.e., iff there's no I between them. (I'm not totally sure that i will always be the larger number, but it appears to be the case).

    def findPermutation(self, s):
        return sorted(range(1, len(s) + 2), cmp=lambda i, j: -('I' not in s[j-1:i-1]))

  • 0
    P

    THANKS FOR YOUR AWESOME SOLUTION


  • 0
    D

    Thanks. Here is C++ version.

    class Solution {
    public:
        vector<int> findPermutation(string s) {
            int n = s.size();
            vector<int> res(n+1);
            for (int i = 0; i <= n; i++)
            {
                res[i] = i+1;
            }
            int Dstart = -1;
            for (int i = 0; i < n; i++)
            {
                if (s[i] == 'D')
                {
                    if (Dstart == -1)
                        Dstart = i;
                    if (i == n-1)
                    {
                        reverse(res.begin()+Dstart, res.end());
                    }
                }
                else
                {
                    if (Dstart != -1)
                    {
                        reverse(res.begin()+Dstart, res.begin()+i+1);
                        Dstart = -1;
                    }
                }
            }
            
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.