Leetcode 100322. 删除星号以后字典序最小的字符串
给你一个字符串 s 。它可能包含任意数量的 ‘’ 字符。你的任务是删除所有的 '’ 字符。
当字符串还存在至少一个 ‘*’ 字符时,你可以执行以下操作:
- 删除最左边的 ‘*’ 字符,同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符,你可以删除它们中的任意一个。
请你返回删除所有 ‘*’ 字符以后,剩余字符连接而成的 字典序最小 的字符串。
删除 * 号左边一个字典序最小的字符,有多个,删除一个,虽是如此,但是还有另一个要求,剩余字符串连接而成的字典序最小,因此要删除离 * 号最近的一个字典序最小的字符。
用一个 26 维的数组保存每个字母出现的位置,遇到星号,查找字典序最小的字符的索引。
但是不能直接删除,如果直接删除会影响保存的索引,因此用一个数组先保存删除的索引,之后从后往前删除。
完整代码
class Solution {
public String clearStars(String s) {
StringBuilder builder = new StringBuilder(s);
List<Integer>[] chars = new List[26];
List<Integer> delete = new ArrayList<>();
for (int i = 0; i < 26; i++) {
chars[i] = new ArrayList<>();
}
for (int i = 0; i < builder.length(); i++) {
if (builder.charAt(i) == '*') {
delete.add(i);
for (int j = 0; j < 26; j++) {
int size = chars[j].size();
if (size > 0) {
int num = chars[j].get(size - 1);
chars[j].remove(size - 1);
delete.add(num);
break;
}
}
} else {
chars[builder.charAt(i) - 'a'].add(i);
}
}
Collections.sort(delete);
for (int i = delete.size() - 1; i >= 0; i--) {
builder.deleteCharAt(delete.get(i));
}
return String.valueOf(builder);
}
}
标签:10,delete,删除,字符,builder,100322,size,Day,字典
From: https://blog.csdn.net/weixin_46091073/article/details/139393233