我可能講的沒有很清楚
用 '*' 來代表已經走過當然沒有問題
我自己在寫的時候也一定是能塞在原本的陣列就塞
問題在有些人會說這是 O(1) 的 extra space
這就很白癡了
其實我這裡把兩個不同的東西混在一起講了
第一個是關於什麼東西可以被當成是常數
我的觀點就是，題目本身的數字是常數
而寫在 constraint 裡的不是
因為，你要嘛完全拒絕使用 big O
堅持一切都有一個實際的數字
N <= 1000 就用 1000 算，
最後要算的就是能不能對所有的合法輸入
都能在給定的時間內跑完
要嘛就是，你可能覺得這個標準不夠一般化
會根據CPU、cache 之類跟機器有關的東西的不同而有很大的差別
所以決定用 big O 來表示一個演算法的好壞
那樣就得接受 constraint 裡的數字能夠無限增長
之所以設下限制只是物理上的限制、以及要能自動化的判斷正確性
所以字母的數量 (26) 不該是常數
第二個是關於 extra space 的問題
即使今天假設字母的數量是有限的，就恰恰是 26 個好了
在這裡的空間複雜度也不該是 O(1)
因為空間複雜度 O(1) 代表的是，
你只需要「記下」常數的資訊
但實際並不是這個樣子
現在只是我們偷用原本陣列沒用到的部份
實際上還是需要 O(n) 的資訊
可以想像今天一個 byte 只有 26 種可能性
在這種情況下，當然也沒有空間給你存其他值
最後一樣要拉出來花 O(n) 的空間
因為本來就要這麼多資訊
回到結論，如果是在寫實際的程式
最關心的依然是實際的物理時間
big O 只是讓你比較好估計
這也是為什麼我看到 O(25n) 這個沒什麼道理寫法覺得很有趣
因為一方面 O(25n) 跟 O(n) 是等價的
但一方面作者覺得 25 在實際執行時不是一個可以忽略的值
所以寫成 O(25n)，讓人一看就知道他的意思