[算法]赎金信

题目

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 你可以假设两个字符串均只含有小写字母。

示例

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

这是一道简单题，没什么说的

class Solution { public boolean canConstruct(String ransomNote, String magazine) { if(magazine.equals("")&&ransomNote.equals("")){ return true; } if(magazine.equals("")){ return false; } if(ransomNote.equals("")){ return true; } //暴力破解。。。 char[]big = magazine.toCharArray(); char[]small = ransomNote.toCharArray(); //减少10M内存 if(big.length<small.length) return false; for(int i=0;i<big.length;i++){ for(int j=0;j<small.length;j++){ //找到两个相等的，则把赎金的对应的字符重置成特殊字符，其实删掉更好，问题是char[]删不到子元素的。 if(big[i]==small[j]){ small[j] = '#'; break; } } } for(char c : small){ //只要有任意一个字符没有被杂志包含，则false,否则true if(c!='#'){ return false; } } return true; } }

暴力破解真恐怖:时间负责度O(n²)

举一反三

排序加双指针:

class Solution { public boolean canConstruct(String ransomNote, String magazine) { char[]r = ransomNote.toCharArray(); char[]m = magazine.toCharArray(); //从小到大洗白白，排好序 Arrays.sort(r); Arrays.sort(m); int i = 0; int j = 0; //双指针，只不过这次不是两头，而是都从左边开始 while(i<r.length&&j<m.length){ //如果两个字符相等，则指针都往后移 if(r[i]==m[j]){ i++; j++; }else if(r[i]>m[j]){ //如果赎金的字符大于了杂志上的，则继续从杂志的字符里往后找 j++; }else{ //如果赎金的字符小于了所有的杂志字符，则可以判定杂志满足不了我。 return false; } } //当循环结束后，如果i == r.length说明对于r中的每个字母都在m中找到对应的字母，此时可以按照题目要求构建出randomNote，返回true，否则返回false return i==r.length; } }

双指针的遍历是线性的，但是排序是线性对数的，所以时间复杂度为O(nlog(n)+mlog(m))，空间复杂度为O(m + n)和暴力破解一致。