查看題目詳情可點擊此處蒸播。
題目
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
Example 1:
Input: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Note:
1 <= S.length <= 20000
S consists only of English lowercase letters.
解題思路
這題的解題思路與 {% post_link leetcode/stack/easy/leetcode題號844_BackspaceStringCompare Backspace String Compare %} 相似，只不過回退的「#」條件替換為了相同字符回退晰赞，當然兩個相同的字符是相鄰的沸毁，每次的比較肯定也是從已讀取字符的最后一位開始，可以使用棧的方式解決烁试。
使用棧的方式解決時犀暑，對字符串進行遍歷讀取入棧中驯击，每次讀取字符時與棧頂元素比較是否相同，相同就進行出棧操作耐亏，直到遍歷完字符串徊都。
同樣也有原地算法的方式解題，與插入排序相似广辰。將字符數(shù)組分成已讀取區(qū)和未讀取區(qū)碟贾，利用兩個指針分別操作兩個區(qū)域，然后遍歷未讀取區(qū)轨域，將讀取到的字符與已讀取區(qū)末尾字符比較（如果已讀取區(qū)已經(jīng)存在字符）袱耽，字符相同的話已讀取區(qū)指針減 1，如果不相同將未讀取區(qū)的當前字符覆蓋至已讀取區(qū)末尾干发，已讀取區(qū)指針增 1朱巨，直至遍歷完字符串。
代碼實現(xiàn)
// by stack
public static String removeDuplicates(String S) {
char[] chars = S.toCharArray();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < chars.length; i++) {
if(stack.empty() || !stack.peek().equals(chars[i])) {
stack.push(chars[i]);
} else {
stack.pop();
}
}
char[] result = new char[stack.size()];
while(!stack.empty()) {
result[stack.size() - 1] = stack.pop();
}
return new String(result);
}
// by in place
public static String removeDuplicatesInPlace(String S) {
char[] chars = S.toCharArray();
int j = 0;
for(int i = 0; i < chars.length; i++) {
if(j == 0 || chars[j - 1] != chars[i]) {
chars[j++] = chars[i];
} else {
j--;
}
}
char[] result = new char[j];
System.arraycopy(chars, 0, result, 0, j);
return new String(result);
}
代碼詳情可點擊查看 我的 GitHub 倉庫
