Nuggets team number online, help you Offer impromptu! Click for details

preface

The last few days did not visit nuggets, also did not have any knowledge of the output. Today just saw the Nuggets launched a daily brush card activity. My hands are very busy these days. So let’s do a simple problem to find the states.

Topic describes

You are given a string s composed of upper and lower case English letters.

In a collated string, two adjacent characters s[I] and s[I +1], where 0<= I <= s.length-2, must satisfy the following conditions:

If S [I] is a lowercase character, s[I +1] cannot be the same uppercase character. If s[I] is an uppercase character, s[I +1] cannot be the same lowercase character. Please tidy up the string. Each time you can select two adjacent characters from the string that meet the above conditions and delete them until the string is clean.

Return the collated string. They guarantee that the answer to the test sample is unique given the constraints given.

Note: Empty strings are also collated strings, even though there are no characters in them.

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Example 1:

Input: s = "leEeetcode" Output: "leetCode" Explanation: Whether you select I = 1 or I = 2 the first time, "leEeetcode" is reduced to "leetcode".Copy the code

Example 2:

Input: s = "abBAcC" Output: "" Explanation: There are many different cases, but all lead to the same result. For example: "abBAcC" - > "aAcC" - > "cC" - > "" "abBAcC "- >" abBA "- >" aA "- >" "Copy the code

Example 3:

Input: s = "s" Output: "s"Copy the code

Tip:

  • 1 <= s.length <= 100
  • The S contains only lowercase and uppercase letters

Their thinking

Seeing this topic, the most direct violent solution is to traverse in turn. If the coordinate I meets the scene described above, the current element and the next element will be skipped. Otherwise, concatenate the current character. If the traversal is complete, the concatenated string length is still equal to the current length. None of the elements meets the preceding scenario. Return the string directly. Otherwise, the logic is still executed.

It’s an obvious recursive logic. So if YOU look at the code for the violent solution, after you go through it because you’re going to have to figure out what the next element is, so you don’t want to go out of bounds you can figure out if the current index is the last index, and if it’s the last index you just concatenate the current element. Since there are no elements behind it, this is obviously not enough for this scenario.

class Solution {
    public String makeGood(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(i==s.length()-1){
                stringBuilder.append(s.charAt(i));
            }
            else if(Character.isUpperCase(s.charAt(i)) && ! Character.isUpperCase(s.charAt(i +1)) && Character.toLowerCase(s.charAt(i)) == s.charAt(i + 1)) {
                i += 1;
            } else if(! Character.isUpperCase(s.charAt(i)) && Character.isUpperCase(s.charAt(i +1)) && Character.toUpperCase(s.charAt(i)) == s.charAt(i + 1)) {
                i += 1;
            } else{ stringBuilder.append(s.charAt(i)); }}// recursive processing
        returns.length() == stringBuilder.length() ? s : makeGood(stringBuilder.toString()); }}Copy the code

The memory consumption and time complexity of recursion is definitely painful, so let’s consider a more elegant implementation of this problem. When iterating through the input string S, select the concatenated string if the required scenario is not met. As shown in the figure:

This is a new stringbWith the old seriesBIf the scene is met, the last element of the new string (the element at the top of the stack) pops up, and the old string moves down the index. The top of the stack for the new stringaWith the old seriesAStill meet the scene, pop-upaElement, traverses the subscript of the old string again +1. When the top of the new string stack and the current character of the old string do not meet the scene. The new string pushes the current character of the old string. This is order n time. Moreover, the stack memory consumption caused by recursion is eliminated.

The final code

class Solution {
    public String makeGood(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (stringBuilder.length() > 0 && Character.toLowerCase(stringBuilder.charAt(stringBuilder.length()-1)) == Character.toLowerCase(s.charAt(i)) && stringBuilder.charAt(stringBuilder.length()-1) != s.charAt(i)) {
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            } else{ stringBuilder.append(s.charAt(i)); }}returnstringBuilder.toString(); }}Copy the code

conclusion

On the first day, do a question to motivate yourself and set a small goal for yourself to complete the daily punching in April.

This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details