这是悦乐书的第212次更新，第225篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第80题（顺位题号是383）。给定一个任意赎金票据字符串和另一个包含所有杂志字母的字符串，如果赎金票据可以从杂志中构建，则写一个函数将返回true;否则，它将返回false。杂志字符串中的每个字母只能在赎金票据中使用一次。例如：
canConstruct（“a”，“b”） - > false
canConstruct（“aa”，“ab”） - > false
canConstruct（“aa”，“aab”） - > true
注意：您可以假设两个字符串仅包含小写字母。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
因为只有小写字母，可以将magazine所使用到的字符存入一个长度为26的数组，然后再去遍历ransomNote所使用到的字符，只要数组中某一位元素小于0，则返回false。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
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 j=0; j<ransomNote.length(); j++) {
if (--arr[ransomNote.charAt(j)-'a'] < 0) {
return false;
}
}
return true;
}
03 第二种解法
思路和第一种解法一样，只不过是将传入的两个字符串先转换成字符数组而已。
此解法的时间复杂度是O(n)，空间复杂度是O(n)。
public boolean canConstruct2(String ransomNote, String magazine) {
int[] arr = new int[26];
char[] note = ransomNote.toCharArray();
char[] maz = magazine.toCharArray();
for (int i=0; i<maz.length; i++) {
arr[maz[i]-'a']++;
}
for (int j=0; j<note.length; j++) {
if (arr[note[j]-'a']-- == 0) {
return false;
}
}
return true;
}
04 第三种解法
使用HashMap，先将magazine所使用的字符以及出现次数分别作为key和value存入其中，然后遍历ransomNote的字符，如果其当前字符在map中存在，并且其value值在减1后依然大于等于0，那么将此字符所对应的value值减1，反之直接返回false。
此解法因为用到了HashMap的contains方法，因此时间复杂度最好情况是O(n)，最坏情况是O(n^2)，空间复杂度是O(n)。
public boolean canConstruct3(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<magazine.length(); i++) {
char c = magazine.charAt(i);
map.put(c, map.getOrDefault(c, 0)+1);
}
for (int j=0; j<ransomNote.length(); j++) {
char c = ransomNote.charAt(j);
if (map.containsKey(c) && map.get(c)-1 >= 0) {
map.put(c, map.get(c)-1);
} else {
return false;
}
}
return true;
}
05 第四种解法
依旧是使用HashMap，但是将第三种解法里面的两个循环压缩到一个循环里。循环遍历的对象依旧是ransomNote，获取当前字符c，同时定义一个变量pos，先判断c是否存在于map中，如果c存在于map中，则获取其对应的value并加1，再重新赋值给pos，如果pos大于magazine的长度，直接返回false。
接着重新获取pos的值，等于当前字符在magazine所在的索引（从pos位开始查找），如果pos等于-1，说明当前在ransomNote使用的字符不存在于magazine中，直接返回false，如果pos不等于-1，则将ransomNote的当前字符作为key，该字符在magazine中出现的pos为value存入map中。
此解法因为用到了HashMap的contains方法，因此时间复杂度最好情况是O(n)，最坏情况是O(n^2)，空间复杂度是O(1)。
public boolean canConstruct4(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : ransomNote.toCharArray()) {
int pos = 0;
if (map.containsKey(c)) {
pos = map.get(c) + 1;
if (pos >= magazine.length()) {
return false;
}
}
pos = magazine.indexOf(c, pos);
if (pos == -1) {
return false;
}
map.put(c, pos);
}
return true;
}
06 小结
算法专题目前已连续日更超过两个月，算法题文章80+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！