去除重复字符串

给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:

输入:"bcabc"输出:"abc"

示例 2:

输入:"cbacdcbc"输出:"acdb"


/*

解题关键:

字典序: 字符串之间比较和数字比较不一样; 字符串比较是从头往后挨个字符比较,那个字符串大取决于两个字符串中第一个对应不相等的字符; 例如 任意一个a开头的字符串都大于任意一个b开头的字符串;例如字典中apple 大于 book;

题目的意思,你去除重复字母后,需要按最小的字典序返回.并且不能打乱其他字母的相对位置;

例如 bcabc 你应该返回abc, 而不是bca,cab;

例如 cbacdcbc 应该返回acdb,而不是cbad,bacd,adcb

例如 zab,应该返回zab,而不是abz;

思路:

1. 判断字符串可能出现的特殊情况

2. 用一个record数组记录字符串中字母出现的次数;

3. 申请一个字符串栈stack用来存储去除重复字母的结果,并利用它的特性帮助我们找到正确的次序;

4. 遍历字符串s

5. 遍历stack 判断当前字符s[i]是否存在于栈stack中

    如果当前字符是否存在于栈的定义一个falg 标记isExist, 0表示不存在, 1表示存在

6.如果isExist存在,record[s[i]]位置上的出现次数减一,并继续遍历下一个字符; 表示当前的stack已经有这个字符了没有必要处理这个重复的字母;

7.如果isExist不存在,则

    如果不存在,则需要循环一个找到一个正确的位置,然后在存储起来;

    如果不存在,跳过栈中所有比当前字符大、且后面还会出现的元素,然后将当前字符入栈

    !stack.isEmpty() 表示栈不为空

    stack.peek() > sCharArray[i]表示栈顶元素比当前元素大

    record[stack.peek()-'a'] > 1表示后面还会出现

通过一个while循环找到将栈中位置错误的数据,出栈. 找当前合适的位置,则结束while循环;

找到合理的位置后,则将当前字符s[i]入栈;

8.直到遍历完所有字符后,则为字符串栈stack

*/

代码下载地址

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 打印结果:[a, b, c]
    小铭铭_7c47阅读 2,744评论 0 0
  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 10,046评论 0 5
  • 题目:去除重复字母(LeetCode-困难)给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字...
    大橘猪猪侠阅读 4,206评论 0 0
  • 知道并下载这个APP,是在微博上看到有一个发的某知名写作者的文章,他在文中透露喜欢写文所以坚持常常在简书上写文发表...
    没有明字阅读 3,610评论 0 0
  • 记事的那天起,我上学了。我还记得第一次进教室,妈妈在外面看着我,我一个人在里面,周...
    空灵_bdc8阅读 1,877评论 0 7

友情链接更多精彩内容