Problem#
給你兩個字串 order 和 s，要你把 s 按照 order 的字母順序排序，沒出現在裡面的字母位置隨意，回傳排序後的字串。
測資限制#
- $1 \le \text{order} \le 26$
- $1 \le \text{s} \le 200$
想法#
Naive: 最簡單就是用 std::sort 加上自訂的 operator< $O(n\log{n})$，sort 完後便是答案。
Improve: 先統計 order 的字母的出現次數 m[ch] = count，接著掃過一次 s[i] = ch，按照 order 的字母出現次數去產生 m[ch] 個 ch 加到答案中；如果 ch 沒出現在 order 中，則直接將 ch 加到答案中。如此一來便只要 $O(n)$ 時間複雜度，便可以得到答案。
AC Code#
Naive#
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(n)$
Improved#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$