Day 14：凯撒密码之Shifting Letters

在开始今天题目之前，先来认识一下凯撒密码 (Caesar cipher)

凯撒密码是一种替换加密技术，明文中的所有字母都在字母表上向後按照一个固定数目进行偏移後被替换成密文。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。 -wiki

先假设今天input string为 'xyz' → 想要每个字母都shift 2 → 得到 'zab'

直觉的想法可能是：
我们先建立一个阵列来存放我们的input，然後呼叫一个shift的function来对这个阵列的字做位移，最後采用join的方式来得到output string。

那我们来思考这个function的实作：
我们可以使用Unicode(万国码)，Unicode给每个字元提供了一个唯一的数位，不论是什麽平台、不论是什麽程序、不论什麽语言。

如果想要对编码有更深入的了解，可以参考了解网页中看不懂的编码：Unicode 在 JavaScript 中的使用

假设我们有记得：
a 的unicode = 97 (10进位)
z 的unicode = 122
我们要把字母转换的行为，其实就是把 **旧的字母 + 偏移量 ⇒ 结果 **

但如我我们今天要把z，位移2後想要得到b，我们理所当然的把122 + 2 = 124 ，此时，实际我们会得到别的符号( | )。

所以，我们应该要把124转换成98，这时候mod(modulo)就派上用场了！
也就是超过122时我们应该回传 96+ (旧的字母 + 偏移量)％122
⇒ 96 + （122 + 2）%122 = 98 (b)

但如果今天我们遇到偏移量shift = 54，我们把 96 + (122+54) % 122 = 140
发现140仍大於 122 (完蛋？)
所以我们应该要再多做一层检查我们的(原偏移量 % 26字母数)来当我们的偏移量

把上面的想法转成程序码就会像下面

function caesarCipherEncryptor(string, key) {
  const result = [];
	const shift = key % 26;
	for (const letter of string){
		result.push(getResult(letter, shift));
	}
	return result.join('');
}

const getResult = (letter, shift) => {
	const newLetterCode = letter.charCodeAt() + shift;
	return newLetterCode <= 122 ? String.fromCharCode(newLetterCode) : String.fromCharCode(96+ (newLetterCode%122));
}

那如果我们根本忘了unicode，我们可以自己建立一个a~z的阵列
这时候 a = 0, z = 25
这时候公式就会变成 -1 + (字母在阵列中的index + 偏移量)％25

Time : O(n), n 是input string size
Space: O(n)

程序码如下

function caesarCipherEncryptor(string, key) {
  const result = [];
	const shift = key % 26;
	const AtoZArr = 'abcdefghijklmnopqrstuvwxyz'.split('');
	for (const letter of string){
		result.push(getResult(letter, shift, AtoZArr));
	}
	return result.join('');
}

const getResult = (letter, shift, AtoZArr) => {
	const newLetterCode = AtoZArr.indexOf(letter) + shift;
	return AtoZArr[newLetterCode % 26] ;
}

还没结束！
别急!让我们仔细阅读一下leetcode的题目，它其实就是我们上面的题目改变一下shift的规则

Input: s = "abc", shifts = [3,5,9]

We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer

其实也就是a，总共会被移动3+5+9的位置；b则是移5+9;c则是只移了9
我们只需要额外对shifts做调整即可，相信看完上面的解说应该有想法了吧！
自己都手试试看吧！
我自己的做法就附在最後面～

const getResult = (letter, shift) => {
  const newLetterCode = letter.charCodeAt() + shift;
  return newLetterCode <= 122 ? String.fromCharCode(newLetterCode) : String.fromCharCode(96 + (newLetterCode % 122));
}

var shiftingLetters = function (s, shifts) {
  let result = [];
  const arrOfs = s.split('')
  // 使用prefix sum技巧
  for (let idx = shifts.length - 2; idx >= 0; --idx) {
    shifts[idx] = (shifts[idx] + shifts[idx + 1]);
  }

  for (let i = 0; i < arrOfs.length; i++) {
    result.push(getResult(arrOfs[i], shifts[i] % 26));
  }
  return result.join('')
};