【字符串】删除小写字母字符串中重复字符

问题描述

删除小写字母字符串中重复字符。如果可以，优先删除重复字符中排在比他小字符前面的字符。 比如，输入：bbcacdww；输出：bacdw

提示：暴力求解效率太低，考虑哈希思想。

问题分析

就是将原来字符串中的相同的删除一个，这个考虑是否需要额外的存储空间，

实现1、空间复杂度为O(1)

void RemoveSame(string& s) { int temp = s[0]; for (size_t i = 1; i < s.size(); ++i) { if (s[i] == temp) s.erase(i, i + 1); else temp = s[i]; } }

实现2、辅助空间不限制

考虑到哈希或者，另外一个相同的存储空间， 遍历原数组，将拷贝到新的存储空间，遇到相同的不拷贝。

void RemoveSame2(string& s) { string temp(s,0,1); for (size_t i = 1; i < s.size(); ++i) { if (temp[temp.size()-1] != s[i]) temp += s[i]; } s = temp; }

哈希表的方法

void RemoveSame3(string& s) { char count[256] = { 0 }; for (size_t i = 0; i < s.size(); ++i) { count[s[i]]++; } int k = 0; for (size_t j = 0; j < 256; ++j) { if (count[j] != 0) s[k++] = j; } s[k] = 0; }