By Long Luo

This article is the solution The Tricky and Clean Solution: Replace Core by 1 of Problem 856. Score of Parentheses.

There are many approaches about this problem, like Stack, Divide and Conquer, Count Cores and so on. Here shows a Tricky and Clean solution.

Intuition

The sum will be a sum of powers of \(2\), as every core (a substring \(()\), with score \(1\) ) will have it’s score multiplied by \(2\) for each exterior set of parentheses that contains that core.

Since \(s\) is a balanced parentheses string, we can replace \(()\) by \(1\), then the result is still a balanced parentheses string.

For example, \((()())\) will become \((1(1))\). The sum is \((1 + 1 \times 2) \times 2 = 1 \times 2 + 1 \times 2 \times 2 = 6\).

As a result, let \(base = 1\), we can make \(base = base \times 2\) when we meet \((\), \(base = base \div 2\) when we meet \((\), and add \(1\) when we meet \(1\).

By Long Luo

This article is the solution 4 Approaches: Stack, Array, Greedy and O(n) Time O(1) Space of Problem 946. Validate Stack Sequences.

Intuition

All elements must be pushed in in order. The key is how to pop them out?

Assuming that the value of the current top element of the stack is \(1\), and the next value to be popped in the corresponding popped sequence is also \(1\), then this value must be popped out immediately. Because the subsequent push will change the top element of the stack to a value other than \(2\), so the popped sequence of the popped numbers does not correspond.

Pushes each number in the pushed queue onto the stack, checking to see if the number is the next value to be popped in the popped sequence, and pops it if so.

Finally, check that not all the popped values are popped.

Stack

We can use a Stack to simulate the process.

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

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (popped == null || pushed.length <= 1) {
        return true;
    }

    int len = pushed.length;
    int popIdx = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        stack.push(pushed[i]);
        while (!stack.empty() && popIdx < len && stack.peek() == popped[popIdx]) {
            stack.pop();
            popIdx++;
        }
    }

    return popIdx == len;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 1249. Minimum Remove to Make Valid Parentheses.

Intuition

First we can use Brute Force to into a two-step` algorithm:

1. find all the \((\) and \()\) and get their indices;
2. determine the indices that need to be deleted;
3. creates a new string from the index of the deleted characters.

We can use a Stack to record the indices of all \((\) and \()\) s. When scanning to the end of the string, all indices remaining in the Stack are \((\) and \()\) s that do not match.

We also need to use a \(\texttt{Set}\) to keep track of unmatched \((\) and \()\) s. Then Delete each character that needs to be deleted according to the indices, and return the recreated string.

The code is as follows:

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 71. Simplify Path .

Intuition

We can just simulate the process from the begin to end.

First we split the given string \(\textit{path}\) into a list of strings by the slash \(/\), denoted as names. According to the canonical path in the problem description, the strings contained in names can only be the following:

1. empty string;
2. a dot .;
3. two dots ..;
4. a directory name containing only English letters, numbers, or _.

If we meet empty string or ., we can ignore them because empty string means nothing, and . means the current directory itself, so we don’t need to change directories.

If we meet .. or “directory names”, we can use a Stack to maintain each directory name in the path. When we encounter “two dots”, we need to change the directory to the parent directory. As the stack is not empty, we pop the directory of the stack. When we encounter a “directory”, we put it to the stack.

Finally we need to iterate each string in names and do the above. After all operations are completed, we connect the strings from the bottom of the stack to the top of the stack with /, and then add / at the top to indicate the root directory, and we can get the simplified Canonical path.

By Long Luo

This article is the solution Easy Backtracking Approach: Deduplicating and Pruning of Problem 39. Combination Sum.

Backtracking

It’s a typical Backtracking algorithm.

We can easily draw the tree below.

Take \(\textit{target} = 7\) as the root node and subtract the value of the edge while creating a child node.

Stop it when the value of the node is \(0\) or a negative number.

All paths from the root node to leaf node \(0\) are the results of the question.

Let’s coding.

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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || target == 0) {
            return ans;
        }

        backtrack(ans, new ArrayList<>(), candidates, target);
        return ans;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int remain) {
        if (remain < 0) {
            return;
        }

        if (remain == 0) {
            res.add(new ArrayList<>(list));
            return;
        }

        int len = candidates.length;
        for (int i = 0; i < len; i++) {
            int num = candidates[i];
            list.add(num);
            backtrack(res, list, candidates, remain - num);
            list.remove(list.size() - 1);
        }
    }
}

Take \(\textit{target} = 7\) for example, \([[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]\) are the answer.

However, the correct answer is \([[7], [2, 2, 3]]\).

Since it requires that each solution is not in order, so the \([2, 2, 3]\) and \([2, 3, 2]\) are the same answer.

What’s problem?

When and how did we duplicate the path?

Why Duplicated?

At each node of the tree, all the candidates were searched and used, so there is a duplicate list.

Is it possible to deduplicate while searching?

Of course we can.

We have to search the elements in order while searching, since the output is not by order. We search from the certain position in the next round.

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

public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int remain) {
    if (remain < 0) {
        return;
    }

    if (remain == 0) {
        res.add(new ArrayList<>(list));
        return;
    }

    int len = candidates.length;
    for (int i = start; i < len; i++) {
        int num = candidates[i];
        list.add(num);
        backtrack(res, list, candidates, i, remain - num);
        list.remove(list.size() - 1);
    }
}

By now we deduplicating it and complete the problem.