383. Ransom Note

[Shawngbk]

解法一：这种解法比较简单，就是将ransomNote的字符串挨个遍历，每个字符再从magazine里遍历匹配，只是再创建了个byte数组，数组每个元素的索引表示magazine字符串的位置，元素值表示是否被校验过，0表示还未被校验过，非0就表示该位置已经被校验过。不过这种做法效率不高。 建立boolean数组flag来记录magazine中的地址，如果访问过了，咱不再访问 public class Solution { public boolean canConstruct(String ransomNote, String magazine) { if(ransomNote.length() > magazine.length()) return false; boolean res = true; boolean[] flag = new boolean[magazine.length()]; for(int i = 0; i < magazine.length(); i++) { flag[i] = false; } //byte[] bytes = new byte[magazine.length()]; for(int i = 0; i < ransomNote.length(); i++) { boolean found = false; char c = ransomNote.charAt(i); for(int j = 0; j < magazine.length(); j++) { if(flag[j] == false && magazine.charAt(j) == c) { found = true; flag[j] = true; //bytes[j]++; break; } } if(!found) { res = found; break; } } return res; } }

解法三：这是LeetCode Discuss中的最热代码，它的原理就是列出了magazine的字母表，然后算出了出现个数，然后遍历ransomNote，保证有足够的字母可用，代码非常清晰。

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