leetcode383. Ransom Note

题目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”) -> falsecanConstruct(“aa”, “ab”) -> falsecanConstruct(“aa”, “aab”) -> true假设有一组字母和一组从杂志中获取的字母，问是否能够用从杂志中获取的字母构成想要的那组字母，要求每个单词只能使用一次。思路一使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母，对应字母位置上的数字减一，每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母，则说明可以找到足够多的字母拼接。 public boolean canConstruct(String ransomNote, String magazine) { if(ransomNote.isEmpty()) return true; if(ransomNote.length() > magazine.length()) return false; int p1 = 0, p2 = 0; int[] count = new int[26]; int wordCount = 0; while(p1 < ransomNote.length() && p2 < ransomNote.length()) { char c1 = ransomNote.charAt(p1); char c2 = magazine.charAt(p2); if(++count[c1-‘a’] == 1) { wordCount++; } if(–count[c2-‘a’] == 0) { wordCount–; } p1++; p2++; } while(p2 < magazine.length()) { if(wordCount == 0) break; char c = magazine.charAt(p2); count[c-‘a’]–; if(count[c-‘a’] == 0) { wordCount–; } p2++; } return wordCount == 0; }思路二：找不到字母就结束思路二利用java的API来查找magazine中从上一个找到的字母开始，下一个字母所在的位置。如果找不到，则说明无法完成拼接。 public boolean canConstruct(String ransomNote, String magazine) { int len=ransomNote.length(); int[] index = new int[128]; for(int i = 0; i < len; i++){ char cu=ransomNote.charAt(i); int result=magazine.indexOf(cu,index[cu]); if(result == -1){ return false; } else{ index[cu]=result + 1; } } return true; }