LeetCode - RemoveDuplicates


刪除相鄰的重複字元

Test Case

Input:abbaca Output:ca

Input:aaaaaaa Output:a

Solution

    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較好

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