Harmless Ransom Note 計算特定字串出現次數

July 24, 2018

concept

// return true/false
function harmlessRansomNote (noteText, magazineText) {
    ...
}

判斷 magazineText 中是否有足夠單詞供 noteText 使用。

example code

  // 為了簡化問題，假設 text 都使用小寫的一般單字
const harmlessRansomNote = (noteText, magazineText) => {
  const noteArray = noteText.split(` `)
  const magazineArray = magazineText.split(` `)

  // hash table like this:
  // {
  //   apple: 1,
  //   cat : 2,
  //   ...
  //	}
  const magazineHashTable = magazineArray.reduce((acc, cur) => {
    acc[cur] = acc[cur] ? acc[cur] + 1 : 1
    return acc
  }, {})

  for (let i = 0; i < noteArray.length; i++) {
    const word = noteArray[i]
    if (magazineHashTable[word]) magazineHashTable[word]--
    else return false
  }
  return true
}

console.log("--------")
console.log(
  harmlessRansomNote(`this is for`, `this is a testing article for testing`)
)
console.log("--------")

Time Complexity

O(n)+O(m) => O(n+m) =>O(n)

有兩個 Linear 迴圈，但是彼此沒有嵌套關係。

實務上，我們最終會把這種函數的時間複雜度寫成 O(n)