Leetcode 0383. 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`.

Easy

Description

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 <= 10^5
• ransomNote and magazine consist of lowercase English letters.

Solution

class Solution:
    # Iteration
    # Time Complexity: BigO(N)
    # Space Complexity: BigO(1)
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(magazine) < len(ransomNote):
            return False
        for char in ransomNote:
            if magazine.find(char) < 0:
                return False
            else:
                magazine = magazine.replace(char, '', 1)
        return True

• find() vs index(): The only difference is that find() method returns -1 if the substring is not found, whereas index() throws an exception.

/**
 * Iteration
 * Time Complexity: BigO(N)
 * Space Complexity: BigO(N)
 */
function canConstruct(ransomNote: string, magazine: string): boolean {
  let store = magazine.split("");
  for (const letter of ransomNote) {
    if (store.includes(letter)) {
      let index = store.indexOf(letter);
      store.splice(index, 1);
    } else return false;
  }
  return true;
}

• String.prototype.indexOf(): returns -1 if the value not found
• May also keep the magazine as a string and replace the character to ‘’:
  E.g. magazine = magazine.replace(letter, '')