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;
}