Last Updated on 2023-04-11 by Clay
題目
ou are given a string s, which contains stars *.
In one operation, you can:
- Choose a star in
s. - Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
- The input will be generated such that the operation is always possible.
- It can be shown that the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e" Output: "lecoe" Explanation: Performing the removals from left to right: - The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e". - The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e". - The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe". There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****" Output: "" Explanation: The entire string is removed, so we return an empty string.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters and stars*.- The operation above can be performed on
s.
題目給定一組字串，我們要做的事情就像是模擬輸入一樣一個個輸入字元，不過在遇到 * 符號時要把前一個字元給刪除。
最終，我們要返回刪除掉不需要字元的全新字串。
解題思路
儲存每一個字元
一開始我很想當然地使用 stack 來操作，想說依序檢查字元，如果是 * 就直接 pop 出最後一項、如果不是則存入字元。
但是後來發現，我要將 stack 的字元拼回字串需要再次顛倒順序，反而花費的時間讓我遇到 TLE 超時問題。
最後換成使用陣列直接來做。
儲存每一個字元 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
string removeStars(string s) {
// Init
vector<char> v;
// Detect '*' and pop the previous character
for (char c: s) {
if (c != '*') {
v.emplace_back(c);
}
else {
v.pop_back();
}
}
// Convert `vector` into `string`
string result(v.begin(), v.end());
return result;
}
};
Python 範例程式碼
class Solution:
def removeStars(self, s: str) -> str:
# Init
v = []
# Detect '*' and pop the previous character
for c in s:
if c == '*' and v:
v.pop()
else:
v.append(c)
# Convert `vector` into `string`
return "".join(v)移動節點
另一個方法比較巧妙，是第一個方法的改進，但是就不需要另外儲存字元了。
其道理非常單純：我們照樣遍歷原始字串，但同時更新一個節點值 i。
這個節點值 i 初始值同樣為 0，在遇到 * 符號前跟遍歷原始字串的索引值是一模一樣的；但是在遇到 * 符號時，便需要將該節點值 i 減去 1，除此之外的情況，則是 s[i] = 當前遍歷到的字元。
下面舉第一個範例來一步步操作。其中 i 是節點值，j 是當前字串的索引值。
Example1: leet**cod*e 012345678910 leet**cod*e i=0, j=0, curr=l l i=1, j=1, curr=e le i=2, j=2, curr=e lee i=3, j=3, curr=t leet i=3-1=2, j=4, curr=* leet i=2-1=1, j=5, curr=* leet i=2, j=6, curr=c lect i=3, j=7, curr=o leco i=4, j=8, curr=d lecod i=4-1=3, j=9, curr=* lecod i=4, j=10, curr=e lecoe
之後只需要取 [0, i] 的字串範圍當作新字串即可。
移動節點 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
string removeStars(string s) {
// Init
int i = 0;
// Detect '*' and pass the previous stored character
for (char c: s) {
if (c == '*') {
--i;
}
else {
s[i++] = c;
}
}
// Convert `vector` into `string`
return s.substr(0, i);
}
};Python 範例程式碼
class Solution:
def removeStars(self, s: str) -> str:
# Init
s = list(s)
i = 0
# Detect '*' and pass the previous stored character
for c in s:
if c == '*':
i -= 1
else:
s[i] = c
i += 1
# Convert `vector` into `string`
return "".join(s[:i])