LeetCode:Ransom Note
【问题再现】
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 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;
}
}
【题后反思】
本题用到了统计字符出现频率的数组计数器，这种实现最为简单，不做解释。
我做这道题的时候考虑了magazine要按照Ransom的顺序，结果一直通不过，把问题想的复杂化了。
public static boolean canConstruct(String ransomNote, String magazine) {
int Sp = 0;
int Lp = 0;
int count = 0;
while (Lp < magazine.length()) {
if(Sp==ransomNote.length())
break;
if (ransomNote.charAt(Sp)==magazine.charAt(Lp)) {
count++;
System.out.print(ransomNote.charAt(Sp));
Sp++;
Lp++;
} else
Lp++;
}
if (count == ransomNote.length())
return true;
else
return false;
这种题目也可以利用HashMap来计算：
public static boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character,Integer> myMap = new HashMap<>();
for(int i=0;i<magazine.length();i++)
{
if(myMap.containsKey(magazine.charAt(i)))
myMap.put(magazine.charAt(i),myMap.get(magazine.charAt(i))+1);
else
myMap.put(magazine.charAt(i),1);
}
for(int i=0;i<ransomNote.length();i++)
{
if(myMap.containsKey(ransomNote.charAt(i)))
{
myMap.put(ransomNote.charAt(i),myMap.get(ransomNote.charAt(i))-1);
if(myMap.get(ransomNote.charAt(i))<=0)
return false;
}
else
return false;
}
return true;
}