iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

30天用JavaScript刷題刷起來!系列 第 14

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('')
};

明日題目預告:來點不一樣的資料結構 Remove Duplicates from linked list,一起換一下口味吧。


上一篇
Day 13 : Maximum Subarray
下一篇
Day 15:Remove Duplicates from linked list
系列文
30天用JavaScript刷題刷起來!30

1 則留言

1
ycchiuuuu
iT邦新手 5 級 ‧ 2021-09-30 12:29:25

推凱撒加密!可以延伸到加密的方式,因為是對稱式加密,是我學加密方式的時候最容易上手的一種~

破解方式也很有趣,26 種英文字母最多只有 25 種偏移量,所以可以暴力產生 25 種偏移後的結果,看哪一段讀起來最像人話,也是一種方法XD

可以參考維基

Jen iT邦新手 5 級 ‧ 2021-09-30 13:32:22 檢舉

“看哪一段讀起來最像人話,也是一種方法XD” 感覺可以生出很多好笑的密文給人猜

TD iT邦新手 4 級 ‧ 2021-10-01 09:26:43 檢舉

不小心點進維基百科一看,發現好多有趣的加密方式,剛剛看到一個對折式的加密 https://zh.wikipedia.org/wiki/%E9%98%BF%E7%89%B9%E5%B7%B4%E5%B8%8C%E5%AF%86%E7%A2%BC

我要留言

立即登入留言