数据结构习题--赎金信

本文主要是介绍数据结构习题--赎金信，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构习题–赎金信

给你两个字符串：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) {// 把其转换为StringBufferStringBuffer note = new StringBuffer(ransomNote);StringBuffer word = new StringBuffer(magazine);// 把赎金信里的每一个字符遍历for (int i = 0; i < note.length(); i++) {// 通过substring进行字符串的截取，然后再去字符区进行寻找// 寻找到，记录其索引位置，否则返回falseint 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;}