C++ Very Easy-to-Understand O(n) Solution with Explanation


  • 0
    F

    My idea is very simple (just read the example first if my explanation is not clear):
    Count how many D's, say k D's, then push the smallest k + 1 available numbers reversely to the result array. For I's it's even simpler, just push the smallest available number to the result array one by one.
    The only exceptional case is when entering I from D, here you need to pop one earlier value. See the example:

    e.g. DDDIIIDDD

    [DDD]IIIDDD ( [] = just scanned characters)
    3 D's, so push the smallest 4 numbers:
    Result:4,3,2,1

    DDD[III]DDD
    3 I's, so push the next 3 smallest numbers, which are 5, 6, 7.
    Result:4,3,2,1,5,6,7,

    DDDIII[DDD]
    3 D's, and the previous one was I. So pop last pushed value 7, and push next 4 smallest numbers: 10, 9, 8, 7
    Result:4,3,2,1,5,6,10,9,8,7

    Done

    Idea is just as easy as this. The implementation takes some attention to get right though.

    class Solution {
    public:
        vector<int> findPermutation(string s) {
            vector<int> result;
            s.push_back('I'); //Force to run one more round after i == s.size()
            int count = 0;
            for (int i = 0; i < s.size(); ++ i)
            {
                if (s[i] == 'D')
                {
                    count ++;
                    continue;
                }
                if (i == 0 || s[i - 1] == 'D' )
                {
                    if (result.size() > 0)
                        result.pop_back();
                    result.push_back(result.size() + count + 1);
                }
                int base = result.size() - 1;
                while (count > 0)
                {
                    result.push_back(base + count);
                    count --;
                }
                result.push_back(result.size() + 1);
            }
            result.pop_back(); // Don't need the additional one.
            return result;
        }
    };
    

Log in to reply
 

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