5/13 每日一題 (b是否是被a組成的字串)

 

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

 

Constraints:

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

class Solution:

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import defaultdict
        freq=defaultdict(int)
        for i in ransomNote:
            freq[i] += 1
        
        for i in magazine:
            if i in freq.keys():
                if freq[i]>0:
                    freq[i] -=1
        if sum(freq.values()) >0:

#只要還有剩餘元素比紹沒有完全又它構成

#p.s他是freq.values物件長這樣dict_values([0, 1]),可以用sum統計
            return False
        else:
            return True

-------------------------------------------------------------

參考解答

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        st1, st2 = Counter(ransomNote), Counter(magazine)
#Counter 是把這字串出現的元素當作key,次數當作value
        if st1 & st2 == st1: 
#st1 & st2 == st1 表示說st1和st2交集的key完全等於st1(也就是st2被st1構成)
            return True
        return False