Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Example 1:


Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]
 

Constraints:

The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Solution

The solution is first to find the node before the left node. Then we reverse the nodes from the left node to the right node. The solution in Leetcode explain how the reverse work step by step, which is very clear and clever.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0);
        // created dummy node
        dummy -> next = head;
        // intialising prev pointer on dummy node
        ListNode* prev = dummy;
        
        // set prev to the node that left to the node "Left"
        for (int i = 1; i < left; i++){
            prev = prev->next;
        }
        // current pointer will be just after prev
        ListNode* current = prev -> next;
        for (int i = 0; i < right-left; i++){
            // forw pointer will be after curr
            ListNode* forward = current -> next;
            current -> next = forward -> next;
            forward -> next = prev -> next;
            prev -> next = forward;
        }
        return dummy->next;
    }
};

Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Example 1:


Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:


Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:



Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
 

Constraints:

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.

My solution

My solution is to use an unordered_map to store the original node and the copied node.

Firstly, we store the original node and a new node with the same value as the original one as the copied node.

1
2
3
4
5
6
7

unordered_map<Node*, Node*> nodeMap;
    Node * current = head;
    while(current){
        // copy the val from the original to a new one
        nodeMap[current] = new Node(current->val);
        current = current -> next;
    }

Secondly, we iterate the linked list from head again, and this time, we set the next pointer and the random pointer of the copied node by looking up the original node in the unordered_map.

1
2
3
4
5
6
7
8
9
10
11

current = head;
while(current){
    if(current->next){
        nodeMap[current]->next = nodeMap[current->next];
    }
    if(current->random){
        nodeMap[current]->random = nodeMap[current->random];
    }
    current = current -> next;
}
return nodeMap[head];

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> nodeMap;
        Node * current = head;
        while(current){
            // copy the val from the original to a new one
            nodeMap[current] = new Node(current->val);
            current = current -> next;
        }
        current = head;
        while(current){
            if(current->next){
                nodeMap[current]->next = nodeMap[current->next];
            }
            if(current->random){
                nodeMap[current]->random = nodeMap[current->random];
            }
            current = current -> next;
        }
        return nodeMap[head];
    }
};

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Example 1:


Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: list1 = [], list2 = []
Output: []
Example 3:

Input: list1 = [], list2 = [0]
Output: [0]
 

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

My solution

The solution is to use a dummy node to simplify the edge cases. Then we use a while loop to iterate through both linked lists. We compare the values of the current nodes of the two linked lists. We add the smaller one to the merged list. Then we move the current pointer of the merged list to the next node. We also move the current pointer of the linked list that we add the node from to the next node. We repeat this process until one of the linked lists is empty. Then we add the rest of the other linked list to the merged list. Then we return the actual head of the merged list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyHead = new ListNode();  // Create a dummy node to simplify edge cases.
        ListNode* current = dummyHead;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        if (list1) {
            current->next = list1;
        } else {
            current->next = list2;
        }
        ListNode* mergedHead = dummyHead->next;  // The actual start of the merged list.
        delete dummyHead;  // Remove the dummy node.
        return mergedHead;
    }
};

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Example 1:


Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
 

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Solution

The solution is to use a linked list to store the sum of two digits. The carry is stored in a variable. The sum of two digits is the sum of the two digits plus the carry. The carry is the sum divided by 10. The sum is the sum mod 10. The sum is the new node of the linked list. The carry is the carry of the next iteration. Once we compute the carry and the sum value, we create a new ListNode with the sum value, and then linked the current Node to this new ListNode, and then set the temp, which is the current node to the next one. The iteration stops when both linked lists are empty and the carry is 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        ListNode* temp = head;
        int carry = 0;
        while (l1 || l2|| carry ){
            int sum = 0;
            if (l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            sum += carry;
            carry = sum/10;
            ListNode *head =  new ListNode(sum%10);
            temp -> next =head;
            temp = temp->next;
        }
        return head -> next;
    }
};

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Example 1:


Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:


Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:


Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
 

Constraints:

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

My solution

My solution is to use an unordered_set to store the linked list that I’ve met. If I meet a node that is already in the set, then I return true. If I reach the end of the linked list, then I return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set <ListNode*> linkSet;
        while(head != NULL){
            if (linkSet.find(head) != linkSet.end())
                return true;
            else
                linkSet.insert(head);
            head = head -> next;
        }
        return false;
    }
};

Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Example 1:

Input: s = "1 + 1"
Output: 2
Example 2:

Input: s = " 2-1 + 2 "
Output: 3
Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
 

Constraints:

1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

Solution

I found a recursive solution to solve this probelm. then main idea is use a recursive function to get the result from the start of the string to the end or the ‘)’ character. It first find the number between operators, then it add the number with the sign to the result value, then it reset the number to 0. If it finds a ‘(‘, it calls the recursive function again to get the result of the expression inside the ‘()’. If it finds a ‘+’, it sets the sign to 1, if it finds a ‘-‘, it sets the sign to -1. If it finds a ‘)’, it returns the result value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <cctype>
class Solution {
public:
    int calculate(string s) {
        int i = 0, N = s.size();
        return dfs(s, i, N);
    }
    
    int dfs(const string& s, int& i, const int& N){
        int res = 0, sign = 1, num = 0;
        while(i < N && s[i] != ')'){
            if(isdigit(s[i]))
                num = num * 10 + (s[i] - '0');
            else{
                res += sign * num;
                num = 0;
                if(s[i] == '+') sign = 1;
                else if(s[i] == '-') sign = -1;
                else if(s[i] == '('){
                    i++;
                    res = res + sign * dfs(s, i, N);
                }
            }
            i++;
        }
        return res + sign * num;
    }
};

Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/‘.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 

Constraints:

1 <= tokens.length <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

My solution with stack

Based on the definition of RPN, I found that we can use a stack to store the values follow the order of the input vector, once we find an operator, we pop the top two values from the stack and calculate the result, then push the result back to the stack. After the iteration, we return the top of the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> RPNstack;
        size_t n = tokens.size();
        for (int i = 0; i < n; i++){
            if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
                int num = stoi(tokens[i]);
                RPNstack.push(num);
            }
            else if(tokens[i] == "+"){
                int temp1 = RPNstack.top();
                RPNstack.pop();
                int temp2 = RPNstack.top();
                RPNstack.pop();
                int result = temp2 + temp1;
                RPNstack.push(result);
            }
            else if(tokens[i] == "-"){
                int temp1 = RPNstack.top();
                RPNstack.pop();
                int temp2 = RPNstack.top();
                RPNstack.pop();
                int result = temp2 - temp1;
                RPNstack.push(result);
            }
            else if(tokens[i] == "*"){
                int temp1 = RPNstack.top();
                RPNstack.pop();
                int temp2 = RPNstack.top();
                RPNstack.pop();
                int result = temp2 * temp1;
                RPNstack.push(result);
            }
            else if(tokens[i] == "/"){
                int temp1 = RPNstack.top();
                RPNstack.pop();
                int temp2 = RPNstack.top();
                RPNstack.pop();
                int result = temp2 / temp1;
                RPNstack.push(result);
            }
        } 
        return RPNstack.top();
    }
};

Solution with unordered_map

I found a solution using unordered_map and stack to solve this problem. One thing I’ve never seen before is the use of unordered_map. I think it is a good way to store the operator and the corresponding function.

When we iterate the vector, if the element is not an operator, we push it into the stack. If it is an operator, we pop the top two elements from the stack and calculate the result by mapping the operator to the responding operation, then push the result back to the stack. After the iteration, we return the top of the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        unordered_map<string, function<int (int, int) > > map = {
            { "+" , [] (int a, int b) { return a + b; } },
            { "-" , [] (int a, int b) { return a - b; } },
            { "*" , [] (int a, int b) { return a * b; } },
            { "/" , [] (int a, int b) { return a / b; } }
        };
        std::stack<int> stack;
        for (string& s : tokens) {
            if (!map.count(s)) {
                stack.push(stoi(s));
            } else {
                int op1 = stack.top();
                stack.pop();
                int op2 = stack.top();
                stack.pop();
                stack.push(map[s](op2, op1));
            }
        }
        return stack.top();
    }
};

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2
 

Constraints:

-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.

My solution

Every function is straight forward and eay to write, except for the getMin() function. I used a vector to store the minimum value of the stack. The method I use is create two vectors (we can use stack of course), one is the main Stack, which I called miniStack, and the other stack is to store the min values, which is miniOrder in my code.

Once we push a value into the stack, we check whether the value is smaller than the top of the miniOrder. If it is, we push the value into the miniOrder and miniStack. If it is not, we only push the value into the miniStack.

Once we try to use pop function, before we pop the value in the mainStack, we first check whether this value is equal to the top of the miniOrder. If it is, we pop the value in the miniOrder and miniStack. If it is not, we only pop the value in the miniStack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class MinStack {
public:
    MinStack() {
        miniStack.clear();
        miniOrder.clear();
    }
    
    void push(int val) {
        miniStack.push_back(val);
        if (miniOrder.empty())
            miniOrder.push_back(val);
        else if(miniOrder.back()>= val)
            miniOrder.push_back(val);
    }
    
    void pop() {
        if(!miniOrder.empty()){
            if (miniOrder.back() == miniStack.back())
                miniOrder.pop_back();
        }
        if (!miniStack.empty())
            miniStack.pop_back();
    }
    
    int top() {
        return miniStack.back();
    }
    
    int getMin() {
        return miniOrder.back();
    }
    private: 
        vector <int> miniStack;
        vector <int> miniOrder;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Given a string path, which is an absolute path (starting with a slash ‘/‘) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//‘) are treated as a single slash ‘/‘. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash ‘/‘.
Any two directories are separated by a single slash ‘/‘.
The path does not end with a trailing ‘/‘.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Example 1:

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
 

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Solutions

The solution is using stack to store the the folder names. If we meet “.”, we just skip it, if we meet “..”, we pop the top of the stack, if we meet a folder name, we push it into the stack. After the iteration, we pop the stack and add the folder names to the answer string. If the answer string is empty, we return “/“. If it is not, we return the answer string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> stack;
        string answer;
        for (int i = 0; i < path.size(); i++){
            if(path[i] == '/')
                continue;
            string temp = "";
            while (i < path.size() && path[i] != '/'){
                temp += path[i];
                i++;
            }
            if (temp == ".") continue;
            else if (temp == ".."){
                if (!stack.empty())
                    stack.pop();
            }
            else{
                stack.push(temp);
            }
        }

        while (!stack.empty()){
            answer = "/" + stack.top() + answer;
            stack.pop();
        }
        if (answer.size() == 0)
            return "/";
        return answer;
        
    }
};

Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

My solution

My solution is to use a stack to store the characters: If the input char is a left parenthes, I push it into the stack. If it is not, we check whether the top of the stack is the corresponding left parenthes. If it is, we pop the top of the stack. If it is not, we return false. Also, I checked whether the stack is empty when the next char is a right parenthes, if it is, we return false because it is invalid. After the iteration, we check whether the stack is empty. If it is, we return true. If it is not, we return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) return true;
        int n = s.size();
        vector<char> stack;
        stack.push_back(s[0]);
        for (int i = 1; i < n; i++){
            if (s[i] == '(' ||s[i] == '{'||s[i] == '[' ){
                stack.push_back(s[i]);
            }
            else if (stack.empty() && s[i]  == ')' || stack.empty() && s[i] == '}' ||stack.empty() && s[i] == ']')
                return false;
            else if (s[i] == ')' && stack[stack.size()-1] == '(' || s[i] == '}' && stack[stack.size()-1] == '{'||s[i] == ']'  && stack[stack.size()-1] == '[' ){
                stack.pop_back();
            }
            else
                return false;
        }
        if (stack.size() == 0)
            return true;
        return false;
    }
};

Improved Solution

I found that I actually use a vector as a stack, so I can use a stack instead.
The main idea of this improved solution is once we have a left paranthes, we can push the responding right paranthes into the stack. Then if we face a right paranthes, we can just compare it to the top of the stack, if it is not equal, return false, if it is equal, we can pop the top. At the end of the iteration, we check whether the stack is empty. If it is, we return true. If it is not, we return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) return true;
        int n = s.size();
        stack<char> stack;
        for (int i = 0; i < n; i++){
            if(s[i] == '{')
                stack.push('}');
            else if(s[i] == '(')
                stack.push(')');            
            else if(s[i] == '[')
                stack.push(']');
            else if (stack.empty() || stack.top() != s[i])
                return false;
            else stack.pop();
        }
        return stack.empty();
    }
};