共计 1450 个字符，预计需要花费 4 分钟才能阅读完成。
题目
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
You may assume that both strings contain only lowercase letters.
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
假设有一组字母和一组从杂志中获取的字母，问是否能够用从杂志中获取的字母构成想要的那组字母，要求每个单词只能使用一次。
思路一
使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母，对应字母位置上的数字减一，每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母，则说明可以找到足够多的字母拼接。
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.isEmpty()) return true;
if(ransomNote.length() > magazine.length()) return false;
int p1 = 0, p2 = 0;
int[] count = new int[26];
int wordCount = 0;
while(p1 < ransomNote.length() && p2 < ransomNote.length()) {
char c1 = ransomNote.charAt(p1);
char c2 = magazine.charAt(p2);
if(++count[c1-‘a’] == 1) {
wordCount++;
}
if(–count[c2-‘a’] == 0) {
wordCount–;
}
p1++;
p2++;
}
while(p2 < magazine.length()) {
if(wordCount == 0) break;
char c = magazine.charAt(p2);
count[c-‘a’]–;
if(count[c-‘a’] == 0) {
wordCount–;
}
p2++;
}
return wordCount == 0;
}
思路二：找不到字母就结束
思路二利用 java 的 API 来查找 magazine 中从上一个找到的字母开始，下一个字母所在的位置。如果找不到，则说明无法完成拼接。
public boolean canConstruct(String ransomNote, String magazine) {
int len=ransomNote.length();
int[] index = new int[128];
for(int i = 0; i < len; i++){
char cu=ransomNote.charAt(i);
int result=magazine.indexOf(cu,index[cu]);
if(result == -1){
return false;
}
else{
index[cu]=result + 1;
}
}
return true;
}
