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化數(shù)組方法
最優(yōu)解
Java折联，O(n)復雜度识颊，統(tǒng)計ransomNote各個字母個數(shù)，和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;
}
}
