iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 28
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 28

Day28-解題-Ransom Note

今天我們要解的題目是 Ransom Note,題目內容如下:

先給定一段句子或是文章,之後再給出一個比較短的句子,若該句子的單字都能從一開始給的文章文章擷取出來的話,就回傳 true,否則回傳 false。

換個比較生活化的說法就是比如報紙上有篇文章,然後要利用文章上的文字把它們剪下來組成一個特定的句子,如果能組成就回傳 true,否則回傳 false。
在此問題中要考慮的是剪下來的字不能重複使用,比如你把 "程式" 剪下放到目標句子裡,之後句子又有出現第二次 "程式" 的話,那就只能再從文章中找,不能用已放到句子裡的 "程式" 那兩個字。

理解題目後我們來實作吧!

  1. 我們先宣告一個 ransomNote() 函式,帶入兩個參數,並且將兩個參數(字串)轉成陣列儲存。然後再宣告一個 result 變數,儲存判斷結果。
function ransomNote(noteStr, articleStr) {
  const noteArr = noteStr.split(' ');
  const articleArr = articleStr.split(' ');
  let result = true;
}
  1. 接著我們要用 JavaScript 物件的特性,去儲存輸入字串的每個單詞和出現的次數。

在 JS 中,物件的屬性一定為字串,比如像這樣: { '1': hi },而物件的值可為數字/字串/null...等,蠻像 Hash table 的概念這樣。

我們使用 if 判斷物件內還沒有某屬性(單字)的話,就建立它,預設值為0,之後再主動加1(代表目前該單字出現一次),下次又出現同個單字時只要值再加1即可。

function ransomNote(noteStr, articleStr) {
  const noteArr = noteStr.split(' ');
  const articleArr = articleStr.split(' ');
  let articleObj = {};
  let result = true;

  articleArr.forEach(word => {
    if (!articleObj[word]) {
      articleObj[word] = 0;
    }
    articleObj[word]++;
  })


  return result;
}
  1. 最後我們將 noteArr 遍歷,將其單字作為 artileObj 的屬性值,如果有存在的話就減1(表示消耗一個單字),找不到單字或單字用完的話就讓結果為 false。
function ransomNote(noteStr, articleStr) {
  const noteArr = noteStr.split(' ');
  const articleArr = articleStr.split(' ');
  let articleObj = {};
  let result = true;

  articleArr.forEach(word => {
    if (!articleObj[word]) {
      articleObj[word] = 0;
    }
    articleObj[word]++;
  })

  noteArr.forEach(word => {
    if(articleObj[word] > 0) {
      articleObj[word]--;
    } else {
      result = false;
    }
  })
  return result;
}

const str = 'Given an arbitrary ransom note string and another string containing letters from all the magazines';

console.log(ransomNote('ransom note', str));
console.log(ransomNote('ransom note note', str));

運行結果如下圖:

這次的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day28-ransom-note.js

鐵人賽即將進入尾聲,明天將會來解"Two Sum"問題!


上一篇
Day27-解題-Caesar Cipher 凱薩密碼
下一篇
Day29-解題-Two Sum
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言