preface

Nuggets in the recent brush topic activities, also come to join in the excitement. This is leetCode’s problem of the day task

Topic describes

Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them. The deduplication operation is repeated on S until the deletion cannot continue. Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

Difficulty: Easy

Example:

Input: “abbaca” Output: “ca”

Explanation: For example, in “abbaca”, we can delete “bb” because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this point. Then we get the string “aaca”, where only “aa” can be deduplicated, so the final string is “ca”.

Tip:

1 <= S.length <= 20000 S The value consists of lowercase letters only.

Their thinking

The first reaction is, isn’t that disarming? If I eliminate adjacent letters every time, I can use the stack, just check the bottom of the stack and eliminate each time, then I will upload the following code with a snap

AC code 1

  public String removeDuplicates(String S) {
        char[] cs = S.toCharArray();
        Stack<Character> stack = new Stack();
        for (int i = 0; i < cs.length; i++) {
            if(! stack.isEmpty() && stack.peek() == cs[i]) { stack.pop(); }else {
                stack.push(cs[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        stack.forEach(character -> {
            sb.append(character);
        });
        return sb.toString();
    }
Copy the code

The result is always contrary to what you want. After looking at the AC result, the score actually ran a full 30ms, and the memory consumption is not low. It is speculated that the stack in and out and traversal took time

So what if we want to make it faster, let’s look beyond the surface, we just want to eliminate the elements in the current string, treat the current string as an array, because if we eliminate the target array can only be smaller than the current array, we can actually operate on the current array, save time and save memory

In the case of abbaca, the index of the array is I, index is 0, and I is 1.

Now because a is different from B, index and I both go down

This step, because it can be eliminated, index has to be backtracked, because I has been eliminated, so I keeps going

I can eliminate that step again, index goes back, I goes back

And then index because if you go back to the starting point, all of the previous nodes have been deleted, and the value is -1, in that case you have to reset the array so that the value at index is the value at I

We end up with the array cabaca in the figure above, where the number of bits up to index is ca

AC code 2

  public String removeDuplicates(String S) {
        char[] cs = S.toCharArray();

        int index = 0;
        for (int i = 1; i < cs.length; i++) {
        	// All previous nodes are eliminated, treating the current node as the first node
            if (index == -1) {
                index = 0;
                cs[index] = cs[i];
                continue;
            }
            if (cs[index] == cs[i]) {
                // Can be eliminated, backtrack
                index--;
            } else {
                // Do not erase, retain datacs[++index] = cs[i]; }}return String.copyValueOf(cs, 0, index + 1);
  }
Copy the code

The AC result is acceptable this time

conclusion

It’s an easy one. But it’s tricky to keep time and space as low as possible

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign