C/C++ Coding Exercise – Ransom Note (unordered_map or array)

ACMer

9 years ago

Two strings are both lowercase letters. Write a function to determine if one string can be constructed using the letters from the other string. For example:

1
2
3

canConstruct("aa", "ab") = false
canConstruct("aa", "aab") = true
canConstruct("a", "b") = false

canConstruct("aa", "ab") = false
canConstruct("aa", "aab") = true
canConstruct("a", "b") = false

Submit your solution at: https://leetcode.com/problems/ransom-note/

Using STL::unordered_map

STL::unordered_map can be seen as an efficient hash data structure. We can record the count of each lowercase appearance and use them by decrementing each counter. If we have a negative counter, it means we cannot construct the note by using the characters from the other string.

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mag;
        for (char x: magazine) {
            if (mag.count(x)) {
                mag[x] ++;
            } else {
                mag[x] = 1;
            }
        }
        for (char x: ransomNote) {
            if (mag.count(x)) {
                mag[x] --;
                if (mag[x] < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mag;
        for (char x: magazine) {
            if (mag.count(x)) {
                mag[x] ++;
            } else {
                mag[x] = 1;
            }
        }
        for (char x: ransomNote) {
            if (mag.count(x)) {
                mag[x] --;
                if (mag[x] < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
};

Using Static Array

Since the given inputs are all lowercase letters, we can construct the counter of 26 elements and implement the same idea but shorter.

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int mag[26] = {0};
        for (char x: magazine) {
            mag[x - 97] ++;
        }
        for (char x: ransomNote) {
            mag[x -97] --;
            if (mag[x - 97] < 0) {
                return false;
            } 
        }
        return true;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int mag[26] = {0};
        for (char x: magazine) {
            mag[x - 97] ++;
        }
        for (char x: ransomNote) {
            mag[x -97] --;
            if (mag[x - 97] < 0) {
                return false;
            } 
        }
        return true;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

274 words
Last Post: How to Prolong Battery Use when Playing Pokemon?
Next Post: How to Define Lambda Functions in C++11?

The Permanent URL is: C/C++ Coding Exercise – Ransom Note (unordered_map or array) (AMP Version)

Using STL::unordered_map

Using Static Array

Related posts: