[每日一题]勒索信

数据结构和算法►字符串 评论

来源

lintcode-勒索信

描述

给定一个任意的表示勒索信内容的字符串，和另一个字符串，表示能从杂志中获取到的所有字符，写一个方法判断能否通过剪下杂志中的字符来构造出这封勒索信，若可以，返回 true；否则返回 false。

杂志字符串中的每一个字符仅能在勒索信中使用一次。

你可以认为两个字符串都只包含小写字母。

样例

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

解题思路

这道题很简单,可以直接在第二个字符串里remove掉第一个字符串的所有字符即可.

但是,还是有一些机智的办法的,那就是老套路,小写字母,那就是只有26个咯,那就可以用数组下标来标识字母啦.然后计数逐一减去即可.

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 勒索信
 */
public boolean canConstruct(String ransomNote, String magazine) {
  //初始化26个小写字母的数组
  int[] letters = new int[26];
  //在杂志中的字符计数
  for (char c : magazine.toCharArray()) {
    letters[c - 'a']++;
  }

  for (char c : ransomNote.toCharArray()) {
    letters[c - 'a']--;
    //如果某个字符数量小于0,则无法完成,false
    if (letters[c - 'a'] < 0) {
      return false;
    }
  }

  return true;
}

完.





ChangeLog

2018-12-18 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。