A string over the characters (, [, ] and ) is said to be valid
if one
can reduce the string to the null string by repeatedly erasing two
consecutive characters of the form () or []. For example, the string
[([])[]] is valid but neither ([)] nor ([ is valid.
Give a polynomial time algorithm to solve the following problem: Given a string, erase the smallest possible number of characters such that the remaining string after the erasures is valid. For example, given the string [(], we can erase ( to get [].
Give a polynomial time algorithm to solve the following problem: Given a string, erase the smallest possible number of characters such that the remaining string after the erasures is valid. For example, given the string [(], we can erase ( to get [].
1 comment :
I suggest using a stack.And each time you get a opening bracket you push to it.. and if u get a closing bracket u check the top. if top is the matching opening bracket you pop it , else if its not the matching bracket then u increase the count (initialized to 0 ) and pop the top element. Finally if the string is over u add the size of the stack to the count .
correct me, i think it might cause problem for some edge cases, but wasn't able to find one. Is this correct ??
Post a Comment