Java 16ms O(m+n) time O(1) space solution


  • 0
    public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int m = ransomNote.length();
        int n = magazine.length();
        if(m>n)return false;
        if(m==0) return true;
        int[] memo = new int [26];
        for(int i = 0;i<n;i++){
            memo[magazine.charAt(i)-'a']++;
        }
        for(int j = 0;j<m;j++){
            if(--memo[ransomNote.charAt(j)-'a']<0) return false;
        }
        return true;
    }
    }

  • 1
    J

    Thanks for sharing. Well, If the characters are all English letters, that works (in this leetcode problem), but if the characters are not limited to the English letters, the vector solution should be replaced with other data structure like unordered_map.


  • 0

    @jtimberlakers
    Thank you for the comment. That is true. If there is not such note:

     You may assume that both strings contain only lowercase letters.
    

    , I probably will use HashMap to solve it.


  • 0
    E

    How does the -'a' thing work exactly. I'm new to ASCII manipulation.


  • 0

    @EbukaPrograms magazine.charAt(i)-'a' will return an integer. All those characters have their own index on the ASCII table from 0 to 255. For instance, 'a' is 97, 'b' is 98 in ASCII. Minus works on these numbers to calculate the "difference(signed)" between the 2 characters. You can convert those char into int to see those indexes like using (int)'a'.


Log in to reply
 

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