This is the sixth day of my participation in the August Text Challenge.More challenges in August

Topic describes

Given a ransom string and a magazine string, determine whether the first string ransom can be formed from characters in the second string magazines. If it can be formed, returntrue; Otherwise returnsfalse. In order not to reveal the handwriting of the ransom letter, search the magazine for the letters needed to form a word to express the meaning. Each character in the magazine string can only be used once in the ransom string. The sample1: Enter: ransomNote ="a", magazine = "b"Output:falseThe sample2: Enter: ransomNote ="aa", magazine = "ab"Output:falseThe sample3: Enter: ransomNote ="aa", magazine = "aab"Output:trueTip: You can assume that both strings contain only lowercase letters. Source: LeetCode//leetcode-cn.com/problems/ransom-noteCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Cycle of violence

  • Start by going through every character on the ransom note, looking for a corresponding character in the magazine
  • If so, delete the character from the magazine and proceed to the next loop
  • If not, directlyreturn false
  • If the traversal ends successfully, thenreturn true
public boolean canConstruct1(String ransomNote, String magazine) {
    for (char c : ransomNote.toCharArray()) {
        if (magazine.contains(String.valueOf(c))) {
            magazine = magazine.replaceFirst(String.valueOf(c), "");
        } else {
            return false; }}return true;
}
Copy the code

2. Number of hash characters

In general, they give two parameters, and find the relationship between two parameter characters, can use hash

  • Iterating through the magazine, storing characters as keys and occurrences as values into the hash table
  • If the character appears more than once, increment value with each occurrence
  • If no value is found in the hash table by character, thenreturn false
  • If you look it up, you subtract value by one
  • If the traversal completes successfully, thereturn true
public boolean canConstruct(String ransomNote, String magazine) {
    Map<Character, Integer> frequency = new HashMap<>();
    for (Character c : magazine.toCharArray()) {
        frequency.put(c, frequency.getOrDefault(c, 0) + 1);
    }
    for (Character c : ransomNote.toCharArray()) {
        if(frequency.get(c) ! =null) {
            if (frequency.get(c) > 1) {
                frequency.put(c, frequency.get(c) - 1);
            } else{ frequency.remove(c); }}else {
            return false; }}return true;
}
Copy the code

3. Semantic array indexes

After writing the first two, I realized that it was taking too long, so I looked at the number one answer and realized that I could have solved the problem using semantic indexes rather than creating hashes.

First of all, the characters in Java correspond to ASCII, and ASCII has 128 elements, 128 numbers, so we can create an array of 128 elements that are ints, and since they are ints, all values in the array will be initialized to 0 by default

If you look at the code, it’s logically similar to the hash solution above, but it’s much more efficient to use arrays

public static boolean canConstruct3(String ransomNote, String magazine) {
    int[] mapArr = new int[128];
    char[] c1 = magazine.toCharArray();
    char[] c2 = ransomNote.toCharArray();
    for (Character c : c1) {
        mapArr[c]++;
    }
    for (Character c : c2) {
        if (mapArr[c] == 0) {
            return false;
        } else{ mapArr[c]--; }}return true;
    }
Copy the code