LeetCode - RemoveDuplicates

發表於 更新於 分類於 閱讀次數： Disqus：

刪除相鄰的重複字元

Test Case

Input:abbaca
Output:ca

Input:aaaaaaa
Output:a

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution
{
    public string RemoveDuplicates(string S)
    {
        var result = new Stack<char>();
        foreach(var s in S)
        {
            if (result.Any())
            {
                if (result.First() == s)
                {
                    result.Pop();
                }
                else
                {
                    result.Push(s);
                }
            }
            else
            {
                result.Push(s);
            }

        }
        return string.Join(string.Empty, result.ToArray().Reverse());
    }
}

心得

這個版本其實是第三個版本，一開始是透過 regex 來做，有點拿大砲轟蚊子的感覺，當然效能也很不好
畢竟 regex 用來處理更複雜的文字結構才是他的優勢

第二個版本依循前一個版本的思路，但沒注意到字串宣告在動態時期的問題，造成記憶體耗費過多的問題

第三個版本的思路比較正確一點，但應該還是有其優化的空間

  1. 判斷集合有無資料，無資料就塞入第一個字元
  2. 集合中若有資料，則判斷目前集合的第一個字元是否與當前字元相符合，相同，則透過 pop()取出
  3. 若不相同，則將當前字元放入集合
  4. 最終 stack 內容即為答案，但因為 stack 的特性所以要先反轉，若用List就不需要反轉了
  1. 字串其實就是 char 的集合，所以直接透過 foreach 迴圈處理
  2. 字串宣告在動態時期都是會另外開闢一個記憶體空間來存放，若需字串處理還是透過StingBuilder較好

其實道理都知道，但真的在做的時候常常還是會忽略這些基本規則，所以還是需要踩一下雷加深記憶