class Solution {
public:
string clearStars(string s) {
}
};
3170. 删除星号以后字典序最小的字符串
给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
'*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
示例 1：
输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
示例 2：
输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。
提示：
1 <= s.length <= 105s 只含有小写英文字母和 '*' 字符。'*' 字符。原站题解
golang 解法, 执行用时: 48 ms, 内存消耗: 7.9 MB, 提交时间: 2024-06-04 10:10:32
func clearStars(s string) string {
del := make([]bool, len(s))
st := [26][]int{}
for i, c := range s {
if c != '*' {
st[c-'a'] = append(st[c-'a'], i)
continue
}
for j, ps := range st {
if m := len(ps); m > 0 {
del[ps[m-1]] = true
st[j] = ps[:m-1]
break
}
}
}
t := []byte{}
for i, d := range del {
if !d && s[i] != '*' {
t = append(t, s[i])
}
}
return string(t)
}
//
func clearStars2(s string) string {
st := [26][]int{}
for i, c := range s {
if c != '*' {
st[c-'a'] = append(st[c-'a'], i)
continue
}
for j, p := range st {
if len(p) > 0 {
st[j] = p[:len(p)-1]
break
}
}
}
idx := []int{}
for _, p := range st {
idx = append(idx, p...)
}
slices.Sort(idx)
t := make([]byte, len(idx))
for i, j := range idx {
t[i] = s[j]
}
return string(t)
}
java 解法, 执行用时: 70 ms, 内存消耗: 46.7 MB, 提交时间: 2024-06-04 10:09:44
class Solution {
public String clearStars(String S) {
char[] s = S.toCharArray();
List<Integer>[] st = new ArrayList[26];
Arrays.setAll(st, i -> new ArrayList<>());
for (int i = 0; i < s.length; i++) {
if (s[i] != '*') {
st[s[i] - 'a'].add(i);
continue;
}
for (List<Integer> p : st) {
if (!p.isEmpty()) {
p.remove(p.size() - 1);
break;
}
}
}
List<Integer> idx = new ArrayList<>();
for (List<Integer> p : st) {
idx.addAll(p);
}
Collections.sort(idx);
StringBuilder t = new StringBuilder(idx.size());
for (int i : idx) {
t.append(s[i]);
}
return t.toString();
}
//
public String clearStars2(String S) {
char[] s = S.toCharArray();
int n = s.length;
boolean[] del = new boolean[n];
List<Integer>[] st = new ArrayList[26];
Arrays.setAll(st, i -> new ArrayList<>());
for (int i = 0; i < n; i++) {
if (s[i] != '*') {
st[s[i] - 'a'].add(i);
continue;
}
for (List<Integer> p : st) {
if (!p.isEmpty()) {
del[p.remove(p.size() - 1)] = true;
break;
}
}
}
StringBuilder t = new StringBuilder();
for (int i = 0; i < n; i++) {
if (!del[i] && s[i] != '*') {
t.append(s[i]);
}
}
return t.toString();
}
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 45.6 MB, 提交时间: 2024-06-04 10:08:57
class Solution {
public:
string clearStars(string s) {
int n = s.length();
vector<int> del(n);
stack<int> st[26];
for (int i = 0; i < n; i++) {
if (s[i] != '*') {
st[s[i] - 'a'].push(i);
continue;
}
for (auto& p : st) {
if (!p.empty()) {
del[p.top()] = true;
p.pop();
break;
}
}
}
string t;
for (int i = 0; i < n; i++) {
if (!del[i] && s[i] != '*') {
t += s[i];
}
}
return t;
}
//
string clearStars2(string s) {
vector<int> st[26];
for (int i = 0; i < s.size(); i++) {
if (s[i] != '*') {
st[s[i] - 'a'].push_back(i);
continue;
}
for (auto& p : st) {
if (!p.empty()) {
p.pop_back();
break;
}
}
}
vector<int> idx;
for (auto& p : st) {
idx.insert(idx.end(), p.begin(), p.end());
}
ranges::sort(idx);
string t(idx.size(), 0);
for (int i = 0; i < idx.size(); i++) {
t[i] = s[idx[i]];
}
return t;
}
};
python3 解法, 执行用时: 371 ms, 内存消耗: 22.2 MB, 提交时间: 2024-06-04 10:08:10
'''
从左到右遍历，26个栈模拟，第i个栈维护第i个小写字母的下标
遇到*时，弹出第一个非空栈的栈顶下标。
最后把所有栈顶下标对应的字母组合起来，即为答案。
'''
class Solution:
def clearStars(self, s: str) -> str:
st = [[] for _ in range(26)]
for i, c in enumerate(s):
if c != '*':
st[ord(c) - ord('a')].append(i)
continue
for p in st:
if p:
p.pop()
break
return ''.join(s[i] for i in sorted(chain.from_iterable(st)))
# 方法二，用一个布尔数组标记需要删除的下标
def clearStars2(self, s: str) -> str:
delete = [False] * len(s)
st = [[] for _ in range(26)]
for i, c in enumerate(s):
if c != '*':
st[ord(c) - ord('a')].append(i)
continue
for p in st:
if p:
delete[p.pop()] = True
break
return ''.join(c for d, c in zip(delete, s) if not d and c != '*')