这题挺有意思的, 但是被 for in 坑了, for (const index in text) {
返回的 index 不是数字而是字符串, 题里很多处用到了 index , 因为这个问题 WA 了好多次…因为逻辑已经感觉没问题了, 就没怎么断点调试, 从代码就能看出来, 加了一堆 console.log
来调试
/**
* @param {string} text
* @return {string}
*/
const smallestSubsequence = function (text) {
const charCount = {};
for (let index in text) {
index = parseInt(index);
charCount[text[index]] ? charCount[text[index]].push(index) : charCount[text[index]] = [index];
}
const charCountKeys = Object.keys(charCount).sort();
const charCountKeysLength = charCountKeys.length;
let res = '';
let last_index = -1;
while (res.length < charCountKeysLength) {
for (let index in charCountKeys) {
index = parseInt(index);
if (is(index, charCountKeys, charCount)) {
res += charCountKeys[index];
last_index = charCount[charCountKeys[index]][0];
// console.log(last_index);
charCountKeys.splice(index, 1)
break;
}
}
for (const char of charCountKeys) {
// console.log(charCount[char], charCount[char][0], last_index);
while (charCount[char] && charCount[char][0] < last_index) {
charCount[char].shift();
}
}
}
// console.log(res);
// console.log(charCountKeys);
// console.log(charCount);
return res;
};
const is = function (i, charCountKeys, charCount) {
// console.log(charCountKeys.length);
for (let j = i + 1; j < charCountKeys.length; ++j) {
// 如果当前字母第一次出现的位置比其他所有字母最后一次出现的位置都靠前才返回 true
// console.log(charCountKeys,j);
// console.log(charCount[charCountKeys[i]][0]);
// console.log(charCount[charCountKeys[j]][charCount[charCountKeys[j]].length - 1]);
if (charCount[charCountKeys[i]][0] > charCount[charCountKeys[j]][charCount[charCountKeys[j]].length - 1]) {
return false;
}
}
return true;
}
更好的解法
string smallestSubsequence(string s, string res = "") {
int cnt[26] = {}, used[26] = {};
for (auto ch : s) ++cnt[ch - 'a'];
for (auto ch : s) {
--cnt[ch - 'a'];
if (used[ch - 'a']++ > 0) continue;
while (!res.empty() && res.back() > ch && cnt[res.back() - 'a'] > 0) {
used[res.back() - 'a'] = 0;
res.pop_back();
}
res.push_back(ch);
}
return res;
}
/**
* @param {string} text
* @return {string}
*/
const smallestSubsequence = function (text) {
// charCount 用来表示 char 的个数
const charCount = new Array(26).fill(0);
// charUse 用来标记一个字符是不是已经在 res 里面了
const charUse = new Array(26).fill(0);
let res = '';
for (const char of text) {
++charCount[char.charCodeAt() - 97];
}
for (const char of text) {
--charCount[char.charCodeAt() - 97];
if (charUse[char.charCodeAt() - 97]++ > 0) continue;
while (!!res.length && res[res.length - 1] > char && charCount[res[res.length - 1].charCodeAt() - 97] > 0) {
charUse[res[res.length - 1].charCodeAt() - 97] = 0;
res = res.slice(0, res.length - 1);
}
res += char;
}
return res;
};