Question

What is wrong in my solution for Leetcode's RansomNote

I am working on the Leetcode problem 383. Ransom Note:

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.

My code passes 98 out of 128 testcases. I created two dictionaries with counts of each occurrence, and wrote some code to compare the two counts.

Here is what I have:

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomdict = {}
        magadict = {}

        for i in ransomNote:
            if i in ransomdict:
                ransomdict[i] +=1
            else:
                ransomdict[i] = 1

        for j in magazine:
            if j in magadict:
                magadict[j] +=1
            else:
                magadict[j] = 1

        print(ransomdict)
        print(magadict)

        for k in ransomdict:
            if k in magadict:
                if magadict[k] >= ransomdict[k]:
                    return True
            else:
                return False

The following test case is supposed to return False, but it is returning True:

ransomNote = "abb"
magazine = "ab" 

To debug, I printed ransomdict and magadict, and clearly the counts are right. What is my mistake?

I know this code isn't optimized; I'm just looking for a way to fix what I am missing here and successfully pass all test cases.

 3  91  3
1 Jan 1970

Solution

 3

Your code is correct. You've only forgotten to write the last return statement properly:

from collections import defaultdict


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomdict = defaultdict(int)
        magadict = defaultdict(int)

        for i in ransomNote:
            ransomdict[i] += 1

        for j in magazine:
            magadict[j] += 1

        for k in ransomdict:
            if k not in magadict or magadict[k] < ransomdict[k]:
                return False

        return True

or simply:

from collections import defaultdict


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomdict = defaultdict(int)
        magadict = defaultdict(int)

        for i in ransomNote:
            ransomdict[i] += 1

        for j in magazine:
            magadict[j] += 1

        return all(ransomdict[char] <= magadict[char] for char in ransomdict)


You can also use Counter() and check Counter(ransomNote) <= Counter(magazine):

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return Counter(ransomNote) <= Counter(magazine)
2024-07-14
user24714692

Solution

 2

The problem with your code is that it can return True while there are still characters to check in ransomdict. This is premature. If you find a letter in ransomdict that occurs enough times in the magazine, this doesn't mean you can stop looking further. You'll first need to check this for all other letters in ransomdict as well.

The only reason to exit the loop early would be when you find a letter that does not occur enough times: then it is right to exit immediately... with False. So the fix is to check the opposite condition (a failure) and return False. Only return True when all tests have been done:

        for k in ransomdict:
            if k in magadict:
                if magadict[k] < ransomdict[k]:  # Opposite condition
                    return False  # Only exit loop when result will be False
            else:
                return False
        return True  # And return True when all letters were verified and OK.

You already know there is room for optimisation, so I just focused on your question for making your approach work.

2024-07-14
trincot