LeetCode——赎金信

LeetCode——赎金信
题目描述:
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断*个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例 1:

输入:ransomNote = “a”, magazine = “b”
输出:false
示例 2:

输入:ransomNote = “aa”, magazine = “ab”
输出:false
示例 3:

输入:ransomNote = “aa”, magazine = “aab”
输出:true

提示:

你可以假设两个字符串均只含有小写字母。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ransom-note
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

解法一:
我先将magazine转换成一个列表便于操作。
然后遍历ransomNote中的每个字符,查看其是否在magazine中,如果在的话,删除magazine中的这个元素并继续循环(因为magazine中每一个字符只能在ransomNote中使用一次)。
如果碰到字符不在magazine中时,就返回False。
循环结束返回True。

解法二:
首先我们判断ransomNote的长度是否大于magazine,如果是则必定返回False。

然后,我们将两个字符串按从小到大的顺序排列好;

定义两个指针i,j,分别指向两个字符串的起始位置;开始循环:

如果两个指针指向的字符匹配,则两个字符同时向前移动一格;
如果指向ransomNote的指针指向的字符更大,则让j指针向前移动一格;
如果i指向的字符更小,则说明j指针之后的所有字符都无法与其匹配(因为两个字符串已经排序好了),这个时候就说明不匹配,返回False。

循环结束后我们还需要判断:ransomNote是否遍历完毕?如果ransomNote还有没遍历到的元素,说明magazine遍历完后ransomNote还有剩余元素,这些元素无法匹配,因此返回False。

*后返回True。

解法一python代码:

class Solution(object):
def canConstruct(self, ransomNote, magazine):
“””
:type ransomNote: str
:type magazine: str
:rtype: bool
“””
m_list = list(magazine)
for r in ransomNote:
if r in m_list:
m_list.remove(r)
else:
return False
return True

解法二python代码:

class Solution(object):
def canConstruct(self, ransomNote, magazine):
“””
:type ransomNote: str
:type magazine: str
:rtype: bool
“””
if len(ransomNote) > len(magazine):
return False
ransomNote = sorted(ransomNote)
magazine = sorted(magazine)
i, j = 0, 0
while i < len(ransomNote) and j < len(magazine):
if ransomNote[i] == magazine[j]:
i += 1
j += 1
elif ransomNote[i] > magazine[j]:
j += 1
else:
return False
if i != len(ransomNote):
return False
return True