1544. 整理字符串

简介: 1544. 整理字符串

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

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

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

  • s[i] 是小写字符,则 s[i+1] 不可以是相同的大写字符。
  • s[i] 是大写字符,则 s[i+1] 不可以是相同的小写字符。

请你将字符串整理好,每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除,直到字符串整理好为止。

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

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "s"
输出: "s"

提示:

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

解题思路

具体实现是通过使用一个数组 res 来模拟栈的行为,遍历字符串 s。对于每个字符,将其与栈顶元素进行比较。如果它们相邻且字符之间的大小写关系满足 Math.abs(s[i].charCodeAt() - res[res.length - 1].charCodeAt()) === 32,即它们的 ASCII 码差值为 32(表示大小写字母之间的关系),则将栈顶元素弹出,并继续比较下一对相邻字符。否则,将当前字符加入到栈中。最后,将栈中的元素转换为字符串并返回。

这段代码的时间复杂度为 O(n),其中 n 是字符串的长度。

AC代码

/**
 * @param {string} s
 * @return {string}
 */
var makeGood = function(s) {
    let res = [s[0]];
    for(let i = 1; i < s.length; i++){
        while(res.length && i < s.length && Math.abs(s[i].charCodeAt() - res[res.length - 1].charCodeAt()) === 32){
            res.pop();
            i++;
        }
        if(i < s.length) res.push(s[i]);
    }
    return res.join('');
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
6月前
|
C++
【C++基础】C-串知识整理
【C++基础】C-串知识整理
37 0
|
5月前
|
机器学习/深度学习 PHP
最全的正则表达式整理
最全的正则表达式整理
51 6
|
前端开发
前端——关于字符串的操作整理
前端——关于字符串的操作整理
|
6月前
常用正则表达式汇总整理
常用正则表达式汇总整理
45 0
C#编程-40:字符串复习笔记
C#编程-40:字符串复习笔记
102 0
C#编程-40:字符串复习笔记
|
程序员
常用正则表达式整理【总结】
平时不太喜欢记忆这些东西,开发的时候需要拿过来直接用就好
119 0
|
JavaScript 前端开发 索引
【重温基础】8.字符串
【重温基础】8.字符串
131 0
|
XML 前端开发 Java
常用正则表达式整理
常用正则表达式整理
279 0
|
机器学习/深度学习 自然语言处理 PHP
正则表达式知识点整理
正则表达式(Regular Expression)就是用某种模式去匹配一类字符串的一种公式。 正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。 正则表达式是繁琐的,但它是强大的,学会之后的应用会让你除了提高效率外,会给你带来绝对的成就感。只要认真阅读本教程,加上应用的时候进行一定的参考,掌握正则表达式不是问题。
|
自然语言处理 算法 Java