从字符串中删除所有重复项并尽可能选择字典序最小的字符串。例如,字符串 cbacdcbc 将返回 acdb,而不是 adcb。
因此,如果我们不必选择字典序最小的字符串,那么这是一个相对简单的解决方案,但考虑到这一事实,我不确定如何得出有效的解决方案。这是我到目前为止所拥有的:
string removeDuplicateLetters(string s)
{
vector<bool> v(26,0);
for(int i = 0; i < s.size(); i++) {
v[s[i]-'a'] = 1;
}
string ss = "";
for(int i = 0; i < s.size(); i++) {
if(v[s[i]-'a']) {
ss += s[i];
v[s[i]-'a'] = 0;
}
}
return ss;
}
最佳答案
算法
- 检查输入字符串中出现了哪些字母:
a,b,c,d
。 - 找到第一个
a
,它后面有所有的b,c,d
。
或者,如果这不可能,请找到第一个b
,它后面有所有a,c,d
。
或者,如果这不可能,请找到第一个c
,它后面有所有a,b,d
。
或者,如果这不可能,请找到第一个d
。 - 丢弃输入字符串的开头到所选字符。
- 从步骤 2 开始重复,找到剩余的字符。
代码示例
(在 Javascript 中;我的 C++ 生锈了)。它创建一个位模式 chars
来存储哪些字符仍然有待找到,并创建一个位模式数组 after
来存储在每个位置之后哪些字符仍然可用。
function smallestString(input) {
var chars = 0, after = [];
for (var i = input.length - 1; i >= 0; i--) {
chars |= 1 << (input.charCodeAt(i) - 97);
after[i] = chars;
}
var result = "", start = 0, pos;
while (chars) {
for (var i = 0; i < 26; i++) {
if (chars & (1 << i)) {
pos = input.indexOf(String.fromCharCode(97 + i), start);
if (chars == (chars & after[pos])) {
result += String.fromCharCode(97 + i);
chars -= 1 << i;
break;
}
}
}
start = pos + 1;
}
return result;
}
document.write(smallestString("cbacdcbc") + "<BR>");
document.write(smallestString("thequickbrownfoxjumpsoverthelazydog"));
关于c++ - 删除重复后选择字典序最小的字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34476853/