leetcode 383. Ransom Note

题干

给定两个字符串，ransomNote,magazine,如果magazine中可以找到ransomNote中字母的全部种类和数量，返回true

思路：

字母无非26个，定义一个26个数大小的数组count[]]，magazine中对应的字母数量为count[]，比如a的数量为count[0],b的数量为count[1]

这就像建立一个仓库一样，接着，如果ransomNote每有一个字母，就在数组中找，如果找到，就减一，表示用掉了，当减一之后为负值时，表示magazine里面已经没有ransomNote的这个字母了，返回false

这种在一方中找另一方的全部的题都可用这种“建仓库”法

代码

由于是字符串，要用到charAt()
java

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int []count=new int [26];
        for(int i=0;i<magazine.length();i++){
            char s=magazine.charAt(i);
            int temp=s-'a';
            if(temp<26)
              count[s-'a']++;
        }
        for(int i=0;i<ransomNote.length();i++){
            if(--count[ransomNote.charAt(i)-'a']<0)
            return false;
        }
        return true;
    }
}

将toCharArray()直接换掉string比起charAt(i)一个个转回更快

        for(char s:magazine.toCharArray()){
            int temp=s-'a';
            if(temp<26)
              count[s-'a']++;
        }
        for(char s:ransomNote.toCharArray()){
            if(--count[s-'a']<0)
            return false;
        }
        return true;
    }
}

python

class Solution:
    def canConstruct(self, ransomNote, magazine):
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

collections.Count()表示会计算参数中的字母种类和个数，如果前者减后者为0，表示前者所有的字母都被后者减掉了，返回0(返回1表示前者还有剩），然后前面加not,返回true，因为这表示后者有前者的所有字母和数量