我可能讲的没有很清楚
用 '*' 来代表已经走过当然没有问题
我自己在写的时候也一定是能塞在原本的阵列就塞
问题在有些人会说这是 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)，让人一看就知道他的意思