C++ 22ms O(m+n) without hash table


  • 0
    B

    Store character counts in array indexed by character binary value. For each character in magazine, increase the corresponding array index by 1. For each character in ransomNote, decrease the corresponding array index by one, and return false if value is <= -1 (i.e. used >= 1 letter more than available). Return true otherwise (note can be constructed).

    bool canConstruct(string ransomNote, string magazine) {
            int chars[256];
            for (int i = 0; i < 256; ++i) {
                chars[i] = 0;
            }
            for (int i = 0; i < magazine.size(); ++i) {
                chars[magazine[i]]++;
            }
            for (int i = 0; i < ransomNote.size(); ++i) {
                chars[ransomNote[i]]--;
                if (chars[ransomNote[i]] <= -1) return false;
            }
            return true;
        }
    

  • 0
    H

    Is there a necessary to not use hash table?
    Is it to do it without adding additional space?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.