数据结构习题–赎金信
给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以,返回 true ;否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
方法
分析
通过对目标内容进行一个字符一个字符的查询,然后在字符区,把已经查找到过的进行剔除
代码
package newbieOfLeetBook;
public class ransomNote {
class Solution {
/**
*
* @param ransomNote 赎金信
* @param magazine 字符区
* @return
*/
public boolean canConstruct(String ransomNote, String magazine) {
// 把其转换为StringBuffer
StringBuffer note = new StringBuffer(ransomNote);
StringBuffer word = new StringBuffer(magazine);
// 把赎金信里的每一个字符遍历
for (int i = 0; i < note.length(); i++) {
// 通过substring进行字符串的截取,然后再去字符区进行寻找
// 寻找到,记录其索引位置,否则返回false
int number = word.indexOf(note.substring(i, i + 1));
if (number == -1){
return false;
}
// 在字符区删除已经使用(被查询到的字符)
word.deleteCharAt(number);
}
return true;
}
}
}
方法:计数统计(推荐)
分析
把已经有的字符统计记入一个数组,然后对目标的字符进行遍历,每遍历一个,就让对应数组的字符的个数减1
亮点:这里的字母都是小写,可以用cnt[word - ‘a’] ,来表示数组的索引,比如当字母为a时,a - a = 0,就是数组第一位
代码
public static boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()){
return false;
}
int[] cnt = new int[26];
for (char word : magazine.toCharArray()){
cnt[word - 'a']++;
}
for (char word : ransomNote.toCharArray()){
if (--cnt[word - 'a'] < 0){
return false;
}
}
return true;
}