LeetCode: Ransom Note
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
#/////////////////////////////////////////////////
# Using an extra hash/dict: O(n) space, O(n) time
#/////////////////////////////////////////////////
magazineDict = {}
for elem in magazine:
if elem in magazineDict:
magazineDict[elem] += 1
else:
magazineDict[elem] = 1
canbeconstructed = True
for item in ransomNote:
if item not in magazineDict:
canbeconstructed = False
break
else:
if magazineDict[item] == 0:
canbeconstructed = False
break
else:
magazineDict[item] -= 1
return canbeconstructed
Given
an
arbitrary
ransom
note
string
and
another
string
containing
letters from
all
the
magazines,
write
a
function
that
will
return
true
if
the
ransom
note
can
be
constructed
from
the
magazines ;
otherwise,
it
will
return
false.
Each
letter
in
the
magazine
string
can
only
be
used
once
in
your
ransom
note.
Note:
You may assume that both strings contain only lowercase letters.
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
#/////////////////////////////////////////////////
# Using an extra hash/dict: O(n) space, O(n) time
#/////////////////////////////////////////////////
magazineDict = {}
for elem in magazine:
if elem in magazineDict:
magazineDict[elem] += 1
else:
magazineDict[elem] = 1
canbeconstructed = True
for item in ransomNote:
if item not in magazineDict:
canbeconstructed = False
break
else:
if magazineDict[item] == 0:
canbeconstructed = False
break
else:
magazineDict[item] -= 1
return canbeconstructed
No comments:
Post a Comment