This looks almost the same as pop stack sequence. So can anyone give a solution of O(N^2)?

  • 0

    Given a stack, if we perform intermixed push/pop operations, we could get scrambled string.
    For example, given "great", if we perform: push, push, pop, pop, push, push, push, pop, pop, pop
    we can get pop sequence like "rgtae", so "rgtae" is a valid scrambled string. And there is no such sequence for "etgar" so "etgar" is not a scrambled string of "great".
    To determine if a sequence is valid only takes O(N^2) (as far as I know) but it cannot handle duplicates. So can anyone give a solution of O(N^2), or at least better than O(N^4)?

  • 1

    Scrambled strings not always can be generated by intermixed push/pop operations. For example the string "abcdefgh" has a scrambled string "abefcdgh", and the nearest string generated by push/pop operations is "abefdcgh".

    By the way, to determine whether a sequence, with no duplicates, can be generated by applying intermixed push/pop operations only takes O(N), using greedy strategy.

Log in to reply

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