383. Ransom Note

C++

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
    if(ransomNote.length()==0) return true;
    sort(ransomNote.begin(),ransomNote.end());
    sort(magazine.begin(),magazine.end());
    cout<<ransomNote<<endl;
    int j=0;
    for(int i=0;j<ransomNote.length()&&i<magazine.length();i++)
    {
        if(magazine[i]==ransomNote[j])
        j++;
    }
    if(j==ransomNote.length()) return true;
    return false;
    }
};

Java

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
    if(ransomNote.equals("")) return true;
    String[] ranArray=ransomNote.split("");
    String[] magArray=magazine.split("");
    Arrays.sort(ranArray);
    Arrays.sort(magArray);
    int j=0;
    for(int i=0;j<ranArray.length&&i<magArray.length;i++)
    {
        if(magArray[i].equals(ranArray[j]))
        j++;
    }
    if(j==ranArray.length) return true;
    return false;
    }
}

Javascript

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    var ranArray=ransomNote.split("");
    var magArray=magazine.split("");
    ranArray.sort();
    magArray.sort();
    var j=0;
    for(var i=0;j<ranArray.length&&i<magArray.length;i++)
    {
        if(magArray[i]===ranArray[j])
        j++;
    }
    if(j===ranArray.length) return true;
    return false;    
};

注意这里各种语言sort的方法和string化数组方法

最优解

Java，O(n)复杂度，统计ransomNote各个字母个数，和magazine比较

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