leetCode Question: Remove Invalid Parentheses

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Analysis:

In this post, I will firstly present the very basic yet workable solutions using BFS, which is implemented in C++.

Then I will explain the DFS solution which is much faster but needs a little more thinking. It is implemented in python.

BFS

First of all, notice that the problem requires all possible results, thus a search algorithm (BFS, or DFS) often would be a good option.

Considering the BFS solution, in this problem we will expand a "tree" with all its child nodes from one level to the other, until we find the leaf nodes we want. So given a string s, the mimimum number of deletion is 0, which is the string itself, also it is the root node of our tree. If it is a valid string, we're done.

Then we expand the tree by delete only 1 parentheses, each child node is one string where 1 parentheses is deleted from the root. Therefore, nodes in this level of tree, represents all possible strings where only 1 parentheses is removed.

We could check each new string and see if it is a valid one. If in current level there is at lease one valid string, the search is terminated after this level is done. Since the minimum of deletion is current level depth, while the possible valid string are all in this level.

For the implementation, we should have:

• A function to check if the string is valid or not.
• A queue for the BFS, which stores the nodes in the same level.
  • Here I use a "map" which we will eliminate the duplicate strings, so that the number of "check" could be reduced.
    Please check the C++ code below for more details.

DFS

Some will notice that in the BFS solution above, the bottleneck is the number of calls for "check". Each time we have to check all the nodes in current level and then go to next level. Alternatively, we could try using DFS.

To reduce the number of "check" being called, we could store the state (true or false) of nodes in each search path. So in next search if we go to the same node, we already have the states, which we don't have to check again.

Also, we could firstly compute the number of '(' and ')' to be removed by counting the parentheses in original string. Notice that after the removal, we still have to check the result string again.

Code (C++):

class Solution {

public:

bool check(string s, int k){

int c = 0;

for (int i=0;i<s.size();i++){

if (i!=k && s[i] == '('){ c+=1; }

if (i!=k && s[i] == ')'){ c-=1; if (c<0){return false;}}

}

return c==0;

}

vector<string> removeInvalidParentheses(string s) {

vector<string> res;

unordered_map<string, bool> mp1;

unordered_map<string, bool> mp2;

if (check(s,-1)){

res.push_back(s);

return res;

}

mp1[s] = true;

while (!mp1.empty()){

bool check_flag = false;

for (auto it1 = mp1.begin();it1!=mp1.end();it1++){

string tmp = it1->first;

for (int i=0; i < tmp.size(); i++){

string tmp2 = tmp;

tmp2.erase(i,1);

if (check(tmp, i) && mp2.find(tmp2) == mp2.end()){

res.push_back(tmp2);

check_flag = true;

}

mp2[tmp2] = true;

}

}

if (check_flag){

return res;

}else{

mp1 = mp2;

mp2.clear();

}

}

return res;

}

};

Code (Python):

class Solution(object):

def check(self, s):

c = 0

for ch in s:

if ch == '(':

c += 1

if ch == ')':

c -= 1

if c < 0:

return False

return c == 0

def dfs(self, s, d_l, d_r, res, hist):

if d_l == 0 and d_r == 0 :

if not s in res and self.check(s):

res[s] = True

elif s == "":

return

else:

for i in range(len(s)):

if not s[0:i] + s[i+1:] in hist:

hist[s[0:i] + s[i+1:]] = True

if s[i] == '(' and d_l > 0:

self.dfs(s[0:i] + s[i+1:], d_l-1, d_r, res, hist)

if s[i] == ')' and d_r > 0:

self.dfs(s[0:i] + s[i+1:], d_l, d_r-1, res, hist)

def removeInvalidParentheses(self, s):

"""

:type s: str

:rtype: List[str]

"""

res = {}

hist = {}

d_r = 0 # number of '(' to be deleted

d_l = 0 # number of ')' to be deleted

for ch in s:

if ch == '(':

d_l += 1

if ch == ')':

if d_l > 0:

d_l -= 1

else:

d_r += 1

self.dfs(s, d_l, d_r, res, hist)

return res.keys()

leetCode Question: Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1

/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Analysis:

In this problem, I have implemented a differrent way of serialization (in C++ code shown below). If you would like to see the simple version which is the same way of LeetCode OJ, please check out the pyhton code below.

Let's first see the simple way of doing this. We will encode the node value level by level, and only encode the "Null" (or "None" in python) node when it is a leaf node. Since we are "searching" the tree level by level, DFS is usually a good way to do so. Here in my solution, I choose to use two queues, to store nodes in current level, and nodes in next level, respectively. For the deserialization, we could still keep two queues for the BFS, and keep track of the node we are expanding.

Secondly, I'l like to show the implementation using a different way. Although it is not a quite efficient method, it still provides good practice of binary tree and binary tree traversal. Particularly, we have a binary tree, rather than the level by level traversal, we still have three depth-first traversal: preorder, inorder, and postorder. Therefore, we could use preorder and inorder traversal to reconstruct the binary tree. Please take a look at my previous post for details. Note that in this problem, there might be duplicate values in different nodes, we have to use the indices of each node for the traversal. So, our encoding format is: "preorder string;inorder string;value string". The "preorder string" is the indices of each node in preorder order, actually, I have given the sequence from 1 to the number of nodes in this string for simplicity. The "inorder string" is the indices of each node in inorder order. The "vaule string" is the values of each node (using preorder order) in string format. All the elements in three strings are splited using ",".

Code (C++):

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Codec {

public:

TreeNode* reconstruct(vector<int>& in, vector<int>& pre, int st, int ed, int& idx, vector<int>& val){

if (idx!=pre.size()){

TreeNode* node = new TreeNode(val[pre[idx]]);

int i=st;

for ( ;i<ed;i++){

if (in[i]==pre[idx]){break;}

}

idx++;

if (i-1 >=st){

node->left = reconstruct(in, pre, st, i-1, idx,val);

}else{

node->left = NULL;

}

if (ed >= i+1){

node->right = reconstruct(in, pre, i+1,ed, idx,val);

}else{

node->right = NULL;

}

return node;

}else{

return NULL;

}

}

void inOrder(TreeNode* root, string& res, string& val, int& i){

if (!root){return;}

inOrder(root->left, res, val, i);

val += to_string(root->val) + ',';

root->val = i;

res += to_string(i) + ',';

i++;

inOrder(root->right,res, val, i);

}

void preOrder(TreeNode* root, string& res){

if (!root){ return; }

res += to_string(root->val) + ',';

preOrder(root->left, res);

preOrder(root->right,res);

}

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

//inorder

string in; //store the inorder tree traversal using index NOT!!! the actural value

string val; //store the actural values of each node according to the "inorder" order

int i=0;

inOrder(root, in, val, i); //inorder traversal

//preorder

string pre; //stroe the preorder tree traversal using index NOT!!! the actural value

preOrder(root, pre); //preorder traversal

//return the encoded string: inorder(index);preorder(index);values

// e.g., Tree [1,2,3,null,null,4,5] returns "0,1,2,3,4,;1,0,3,2,4,;2,1,4,3,5,"

return in + ";" + pre+ ";" + val;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

// decode the string

int pos_1 = data.find(';');

string in = data.substr(0,pos_1);

string tmp = data.substr(pos_1+1);

int pos_2 = tmp.find(';');

string pre = tmp.substr(0,pos_2);

string val = tmp.substr(pos_2+1);

vector<int> in_vec; // save the index of inorder traversal

vector<int> pre_vec; // save the index of preorder traversal

vector<int> val_vec; // save the values according to the inorder order

while (val.find(',')!=-1){

val_vec.push_back(stoi(val.substr(0,val.find(','))));

val = val.substr(val.find(',')+1);

}

while (in.find(',')!=-1){

in_vec.push_back(stoi(in.substr(0,in.find(','))));

in = in.substr(in.find(',')+1);

}

while (pre.find(',')!=-1){

pre_vec.push_back(stoi(pre.substr(0,pre.find(','))));

pre = pre.substr(pre.find(',')+1);

}

// reconstruct tree using preorder and inoreder traversal

int idx = 0;

return reconstruct(in_vec, pre_vec, 0, in_vec.size(),idx, val_vec);

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

Code (Python):

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Codec:

def serialize(self, root):

"""Encodes a tree to a single string.

:type root: TreeNode

:rtype: str

"""

q1 = []

q2 = []

res = ""

q1.append(root)

while True:

while len(q1) != 0:

tmp = q1.pop(0)

if tmp is None:

res += "null,"

else:

res += str(tmp.val) + ","

q2.append(tmp.left)

q2.append(tmp.right)

if len(q2) == 0:

break

q1 = q2[:]

q2 = []

return res

def deserialize(self, data):

"""Decodes your encoded data to tree.

:type data: str

:rtype: TreeNode

"""

data_list = data[0:-1].split(',') # [0:-1] eliminates the last ','

mp1 = []

mp2 = []

head = None

if data_list[0] != "null":

mp1.append(TreeNode(int(data_list[0])))

head = mp1[0]

i = 1

while i < len(data_list):

for node in mp1:

if node is not None:

if data_list[i] != "null":

node.left = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.left)

if data_list[i] != "null":

node.right = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.right)

mp1 = mp2[:]

mp2 = []

return head

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))