[Java][LeetCode][Array] Ransom Note #383

SP Hou
1 min readJul 6, 2022

--

這題很簡單,所以很有時間可以試試看三種寫法,分別是Map, Array與雙指針。
Map:
遍歷一次magazine的字元並放到map計數,再走一次ransomNote的字元並將在map中的字元逐一減去,直到字元不在map中就回false。
Array:
開一個26大小的整數陣列,遍歷一次magazine並轉換成數字,在對映的index位置做計數,遍歷一次ransomNote轉換成數字,當找到陣列中的位置值為0即回false。
Two Pointers:
將兩個字串先轉成字元陣列並做sort,一個指針指在ransomNote,一個指針指在magazine,將字元轉換成數字,向右移動較小數的那個指針,當兩者值相等,計數+1,最後比對count是否與ransomNote長度相同。
HashMap 因為要remove,所以比較慢。

This is a simple problem. I tried three approaches: Map, Array, and Two Pointers.
Map:
Traversal characters of the magazine and put in a map to count. Traversal characters of the ransomNote and subtract one by one, until I can’t find the character in the map, return false.
Array:
Create an Array and the size is 26. Traversal character of the magazine and convert characters to numbers. Count the number and put the value to the index of the Array. Traversal ransomNote and convert characters to numbers. Subtract the count of the index of the array. When the value is 0, return false.
Two Pointers:
Sorted two character arrays first. Create two points, one is for rasomNote, and one is for the magazine. I compare two values of pointers and forward the point of the lesser to next. When two values are equal, the count plus one. Until a point out one of a boundary, end the while loop. At the last, return the result that is from comparing the count and length of the rasomNote.

--

--

No responses yet