題目問
有一個 ransom string,還有一個magazine string
然後要求是不是能從magazine string裡面湊出ransom string裡面要用的所有
characters,而且從magazine string找出的character只能在ransom string裡用一次
比如說ransom string="hello"
magazine string="heeollo"
這樣就應該傳回true
第一解是說在兩個string都去算character counts, 如果對每個字母,magazine string
的character count比ransom string的character counter都高 那就是true
以上為例 ransom string的o有1個, magazine string的o有兩個 所以true
第二解是說 若magazine string超長 那我們是不是可以先把ransom string的char
counts算出來 然後在慢慢掃過magazine string. 遇到一個character就把他對映在
ransom string的char count減一
以剛剛的例子, hello會產生出以下的char counts
h-->1
e-->1
l-->2
o-->1
然後呢, 在掃magazine string,先遇到h,就把h的countr減一 變
h-->0
e-->1
l-->2
o-->1
再遇到e,再把e的counter減一,變
h-->0
e-->0
l-->2
o-->1
再遇到e,因為counter已經是0了 就不變了
用這樣的方法 就可以不用traverse所有的magazine string.所以會比第一解要好
