Ransom Note(383)

题目: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 boolean canConstruct(String ransomNote, String magazine) {
  int[] table = new int[26];
  for (char c : magazine.toCharArray()) {
    table[c - 'a']++;
  }
  for (char c : ransomNote.toCharArray()) {
    table[c - 'a']--;
    if (table[c - 'a'] < 0) {
      return false;
    }
  }
  return true;
}

顺序遍历一个数组的速度比较快,因为数据就是顺序存储在磁盘上的。如果对于每个ransomNote中的字符去magazine中进行查找并替换成"",这样的效率太慢了。

在此记录一下,当遇到字符统计问题时都可以考虑下是否用一个长度为26的数组来存放字符出现次数,这样可以很大程度提高算法的运行效率。

上一篇:JVM基础和调优(六)


下一篇:sencha touch Ext.app.Application