[問題] 面試問題followup

[phoenixrace (殘存亦陌路 兵敗如山倒)]

問題是給你一串字串,相鄰兩個字母是一樣的要消掉.

Example1:
"aabccb" --> "" (全部消完)

Example2:
"add" --> "a" ("dd"可以消掉)

我的解法是用stack, 解完後面試官要求只用 O(1)space, 我就沒想到該怎麼解...

請問有人知道只用 O(1)space 解這題嗎

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.251.165.125
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1539722570.A.162.html
推 DJWS: 有阿  就是面試官  為何不當場問他或者寄信問他
我有跟他要hint, 他說用pointer,不過到現在還是沒想出來, 所以我猜是不是用pointer simulate stack
※ 編輯: phoenixrace (24.251.165.125), 10/17/2018 07:06:03
推 DJWS: 那麼接下來你可以寄信跟他要code
推 FRAXIS: 就把 input array 當 stack 用 然後用一個 index 維護
→ FRAXIS: 還沒處理過的部分
推 DJWS: 所以說 in-place => O(1) space ?
→ phoenixrace: 感謝Fraxis，我還真的沒有想到input string是mutabl
→ phoenixrace: e，感謝開示，這樣應該可以用兩個pointer做到
→ FRAXIS: 一般來說 in-place 就是 O(1) space
→ FRAXIS: 精確來說是 O(1) variables
→ FRAXIS: 因為輸入陣列長度是 n 的話 存 index 就要O(lg n) bits
→ FRAXIS: 不過面試官大概不會注意這種差異..
推 DJWS: 了解  謝謝
推 alan23273850: 我想問這題和 C/C++ 板的 #1Rf8aTlF 這篇差在哪
→ alan23273850: 那邊有很多人討論這題，也萌生出一些解法，不過還沒
→ alan23273850: 看到有 O(1) space 的
推 ckc1ark: 連續兩個以上可以刪 和 連續兩個 有差別