[演算法題目] Caesar Cipher Encryptor

本題資訊

難度：easy
使用語言：C++
相關概念：Strings

題目敘述

Given a non-empty string of lowercase letters and a non-negative integer representing a key, write a function that returns a new string obtained by shifting every letter in the input string by k positions in the alphabet, where k is the key.
Note that letters should “wrap” around the alphabet; in other words, the letter z shifted by one returns the letter a.

Input:

string = "xyz"
key = 2

Output:

"zab"

這一題還蠻經典的簡單題型，也是剛學密碼學一定都聽過的加密技術：凱撒密碼。原理就是將欲加密的文件每個字母都向後或向前移一個固定數目。雖然他的原理過於簡單，以現今的技術來說太容易破解，但在資料處理的練習上還算是蠻基礎又有趣的題型。

Idea

遇到這種字母轉換的問題，第一個一定是想到能用 ASCII code 解決就用 ASCII code（順便補充：A=65、a=97），這樣向後移兩位就是 +2 就好。

再來是考慮到 y 以及 z 字母向後移兩位要再返回字母表的最開始，所以原先我要特別處理超過 122 的狀況。不過一切都想得太複雜了！字母固定 26 個，我們可以利用餘數的概念去處理比較快。

為了讓 a 成為開頭，處理字串的時候會先減掉 'a'，再加上 key（向後移的位數）。

除以 26 後的餘數就等於他們所代表的字母 index，記得最後再把 'a' 加回去。

using namespace std;

string caesarCypherEncryptor(string str, int key) {
  vector<char> newStr;

  for (int i = 0; i < str.size(); i++){
    int k = (str[i] - 'a' + key) % 26 + 'a';
    newStr.push_back((char)k);
  }
  return string(newStr.begin(), newStr.end());
}

時間複雜度：\(O(n)\)，\(n\) 是 str 長度
空間複雜度：\(O(n)\)