算法 leetcode algorithm

LeetCode每日一题--整理字符串

leetCode算法系列

Posted by maybelence on 2021-04-08

前言

最近几天没逛掘金，也没有任何知识上的输出。今天刚上就看到掘金又发起了每日刷题打卡的活动。正好这几天手很颓。先做一个简单题来寻找一下状态。

题目描述

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要满足如下条件:

若 s[i] 是小写字符，则 s[i+1] 不可以是相同的大写字符。
若 s[i] 是大写字符，则 s[i+1] 不可以是相同的小写字符。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/make-the-string-great
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

1
2
3
输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。

示例 2：

1
2
3
4
5
输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

示例 3：

1
2
输入：s = "s"
输出："s"

提示：

  • 1 <= s.length <= 100
  • s 只包含小写和大写英文字母

解题思路

看到这个题目，最直接想到的暴力解法就是依次遍历，如果出现坐标 i 满足上述述场景就跳过当前元素和下一个元素。否则拼接当前字符。如果遍历结束，拼接后的字符串长度仍然等于当前长度。说明没有任何元素满足上述场景。直接返回该字符串。否则仍然执行该逻辑。

很明显的一个递归逻辑。直接看一下暴力解的代码，遍历的之后因为后面要判断下一个元素，防止下标越界可以先判断一下当前下标是不是最后一个下标，如果是最后一个下标就直接拼接当前元素。因为后面没有元素，显然也就不满足这种场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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));
            }
        }
        //递归处理
        return s.length() == stringBuilder.length() ? s : makeGood(stringBuilder.toString());
    }
}

递归的内存消耗和时间复杂度无疑非常令人痛苦，那就接着考虑一下这题有没有更优雅一点的实现方案。在依次遍历输入字符串 s 的时候，如果不满足要求场景，选择拼接字符串。
如图所示：

未命名文件 (2).png
这是新串的 b 与老串的 B 满足场景，弹出新串最后一个元素（栈顶元素），老串顺移下标。此时新串的栈顶 a 与老串的 A 仍满足场景，弹出 a 元素,遍历老串的下标再次+1。当新串栈顶与老串当前字符不满足场景时。新串入栈老串的当前字符。这种做法时间复杂度只有 O(n) 。而且省去了递归造成的栈内存损耗。

未命名文件 (3).png

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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));
            }
        }
        return stringBuilder.toString();
    }
}

总结

今天打卡第一天，先做一题激励一下自己，先给自己定个小目标，完成4月份每日打卡。

本文正在参与「掘金 2021 4 月刷题打卡」, 点击查看 活动详情

Copyright by @maybelence.

沉溺 (你让我的心不再结冰）

邹沛沛

00:00
00:00
标签
算法 leetcode algorithm
其他常用