Remove All Adjacent Duplicates In String
Here is the problem: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
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 <= 20000Sconsists only of English lowercase letters.
Given the S.length off the order of 20K, an N^2 solution would be intractable. Best is to think about this problem as a Stack Problem, but not exactly the same implementation. As you copy elements from S to the solution string, check whether S[i] is the same as the last char in the solution string - if so don't copy it and remove the last from the solution string, otherwise copy it over. In order to avoid the overhead of string manipulation, use StringBuilder. Code is below, cheers, ACC.
public class Solution
{
public string RemoveDuplicates(string S)
{
if (String.IsNullOrEmpty(S)) return S;
StringBuilder sb = new StringBuilder(S);
int sbIndex = 0;
for (int i = 0; i < S.Length; i++) { if (sbIndex - 1>= 0 && sb[sbIndex - 1] == S[i])
{
sbIndex--;
}
else
{
sb[sbIndex] = S[i];
sbIndex++;
}
}
return sb.ToString().Substring(0, sbIndex);
}
}
Comments
Post a Comment
[γγ¬γΌγ ]